Class HenselMultUtil

java.lang.Object
edu.jas.ufd.HenselMultUtil
public class HenselMultUtil extends Object
Hensel multivariate lifting utilities.

  • Field Details

    • logger

      private static final org.apache.logging.log4j.Logger logger

    • debug

      private static final boolean debug

  • Constructor Details

    • HenselMultUtil

      public HenselMultUtil()

  • Method Details

    • liftDiophant

      public static <MOD extends GcdRingElem<MOD> & Modular> List<GenPolynomial<MOD>> liftDiophant(GenPolynomial<MOD> A, GenPolynomial<MOD> B, GenPolynomial<MOD> C, List<MOD> V, long d, long k) throws NoLiftingException
      Modular diophantine equation solution and lifting algorithm. Let p = A_i.ring.coFac.modul() and assume ggt(A,B) == 1 mod p.
      Parameters:
      A - modular GenPolynomial, mod p^k
      B - modular GenPolynomial, mod p^k
      C - modular GenPolynomial, mod p^k
      V - list of substitution values, mod p^k
      d - desired approximation exponent (x_i-v_i)^d.
      k - desired approximation exponent p^k.
      Returns:
      [s, t] with s A' + t B' = C mod p^k, with A' = B, B' = A.
      Throws:
      NoLiftingException

    • liftDiophant

      public static <MOD extends GcdRingElem<MOD> & Modular> List<GenPolynomial<MOD>> liftDiophant(List<GenPolynomial<MOD>> A, GenPolynomial<MOD> C, List<MOD> V, long d, long k) throws NoLiftingException
      Modular diophantine equation solution and lifting algorithm. Let p = A_i.ring.coFac.modul() and assume ggt(a,b) == 1 mod p, for a, b in A.
      Parameters:
      A - list of modular GenPolynomials, mod p^k
      C - modular GenPolynomial, mod p^k
      V - list of substitution values, mod p^k
      d - desired approximation exponent (x_i-v_i)^d.
      k - desired approximation exponent p^k.
      Returns:
      [s_1,..., s_n] with sum_i s_i A_i' = C mod p^k, with Ai' = prod_{j!=i} A_j.
      Throws:
      NoLiftingException

    • isHenselLift

      public static <MOD extends GcdRingElem<MOD> & Modular> boolean isHenselLift(GenPolynomial<BigInteger> C, GenPolynomial<MOD> Cp, List<GenPolynomial<MOD>> F, List<GenPolynomial<MOD>> L)
      Modular Hensel lifting algorithm on coefficients test. Let p = f_i.ring.coFac.modul() and assume C == prod_{0,...,n-1} f_i mod p with gcd(f_i,f_j) == 1 mod p for i != j
      Parameters:
      C - integer polynomial
      Cp - GenPolynomial mod p^k
      F - = [f_0,...,f_{n-1}] list of monic modular polynomials.
      L - = [g_0,...,g_{n-1}] list of lifted modular polynomials.
      Returns:
      true if C = prod_{0,...,n-1} g_i mod p^k, else false.

    • liftHenselMonic

      public static <MOD extends GcdRingElem<MOD> & Modular> List<GenPolynomial<MOD>> liftHenselMonic(GenPolynomial<BigInteger> C, GenPolynomial<MOD> Cp, List<GenPolynomial<MOD>> F, List<BigInteger> V, long k) throws NoLiftingException
      Modular Hensel lifting algorithm, monic case. Let p = A_i.ring.coFac.modul() and assume ggt(a,b) == 1 mod p, for a, b in A.
      Parameters:
      C - monic GenPolynomial with integer coefficients
      Cp - GenPolynomial mod p^k
      F - list of modular GenPolynomials, mod (I_v, p^k )
      V - list of integer substitution values
      k - desired approximation exponent p^k.
      Returns:
      [g'_1,..., g'_n] with prod_i g'_i = Cp mod p^k.
      Throws:
      NoLiftingException

    • liftHensel

      public static <MOD extends GcdRingElem<MOD> & Modular> List<GenPolynomial<MOD>> liftHensel(GenPolynomial<BigInteger> C, GenPolynomial<MOD> Cp, List<GenPolynomial<MOD>> F, List<BigInteger> V, long k, List<GenPolynomial<BigInteger>> G) throws NoLiftingException
      Modular Hensel lifting algorithm. Let p = A_i.ring.coFac.modul() and assume ggt(a,b) == 1 mod p, for a, b in A.
      Parameters:
      C - GenPolynomial with integer coefficients
      Cp - GenPolynomial C mod p^k
      F - list of modular GenPolynomials, mod (I_v, p^k )
      V - list of integral substitution values
      k - desired approximation exponent p^k.
      G - list of leading coefficients of the factors of C.
      Returns:
      [g'_1,..., g'_n] with prod_i g'_i = Cp mod p^k.
      Throws:
      NoLiftingException

    • liftHenselFull

      public static <MOD extends GcdRingElem<MOD> & Modular> List<GenPolynomial<MOD>> liftHenselFull(GenPolynomial<BigInteger> C, List<GenPolynomial<MOD>> F, List<BigInteger> V, long k, List<GenPolynomial<BigInteger>> G) throws NoLiftingException
      Modular Hensel full lifting algorithm. Let p = A_i.ring.coFac.modul() and assume ggt(a,b) == 1 mod p, for a, b in A.
      Parameters:
      C - GenPolynomial with integer coefficients
      F - list of modular GenPolynomials, mod (I_v, p )
      V - list of integer substitution values
      k - desired approximation exponent p^k.
      G - = [g_1,...,g_n] list of factors of leading coefficients.
      Returns:
      [c_1,..., c_n] with prod_i c_i = C mod p^k.
      Throws:
      NoLiftingException