HenselUtil
edu.jas.ufd

Class HenselUtil



  • public class HenselUtilextends Object
    Hensel utilities for ufd.
    • Constructor Detail

      • HenselUtil

        public HenselUtil()
    • Method Detail

      • liftHensel

        public static <MOD extends GcdRingElem<MOD> & ModularHenselApprox<MOD> liftHensel(GenPolynomial<BigInteger> C,                                                                   BigInteger M,                                                                   GenPolynomial<MOD> A,                                                                   GenPolynomial<MOD> B,                                                                   GenPolynomial<MOD> S,                                                                   GenPolynomial<MOD> T)                                                                      throws NoLiftingException
        Modular Hensel lifting algorithm on coefficients. Let p = A.ring.coFac.modul() = B.ring.coFac.modul() and assume C == A*B mod p with gcd(A,B) == 1 mod p and S A + T B == 1 mod p. See Algorithm 6.1. in Geddes et.al.. Linear version, as it does not lift S A + T B == 1 mod p^{e+1}.
        Parameters:
        C - GenPolynomial
        A - GenPolynomial
        B - other GenPolynomial
        S - GenPolynomial
        T - GenPolynomial
        M - bound on the coefficients of A1 and B1 as factors of C.
        Returns:
        [A1,B1,Am,Bm] = lift(C,A,B), with C = A1 * B1 mod p^e, Am = A1 mod p^e, Bm = B1 mod p^e .
        Throws:
        NoLiftingException
      • liftHensel

        public static <MOD extends GcdRingElem<MOD> & ModularHenselApprox<MOD> liftHensel(GenPolynomial<BigInteger> C,                                                                   BigInteger M,                                                                   GenPolynomial<MOD> A,                                                                   GenPolynomial<MOD> B)                                                                      throws NoLiftingException
        Modular Hensel lifting algorithm on coefficients. Let p = A.ring.coFac.modul() = B.ring.coFac.modul() and assume C == A*B mod p with gcd(A,B) == 1 mod p. See algorithm 6.1. in Geddes et.al. and algorithms 3.5.{5,6} in Cohen.
        Parameters:
        C - GenPolynomial
        A - GenPolynomial
        B - other GenPolynomial
        M - bound on the coefficients of A1 and B1 as factors of C.
        Returns:
        [A1,B1] = lift(C,A,B), with C = A1 * B1.
        Throws:
        NoLiftingException
      • liftHenselQuadratic

        public static <MOD extends GcdRingElem<MOD> & ModularHenselApprox<MOD> liftHenselQuadratic(GenPolynomial<BigInteger> C,                                                                            BigInteger M,                                                                            GenPolynomial<MOD> A,                                                                            GenPolynomial<MOD> B,                                                                            GenPolynomial<MOD> S,                                                                            GenPolynomial<MOD> T)                                                                               throws NoLiftingException
        Modular quadratic Hensel lifting algorithm on coefficients. Let p = A.ring.coFac.modul() = B.ring.coFac.modul() and assume C == A*B mod p with gcd(A,B) == 1 mod p and S A + T B == 1 mod p. See algorithm 6.1. in Geddes et.al. and algorithms 3.5.{5,6} in Cohen. Quadratic version, as it also lifts S A + T B == 1 mod p^{e+1}.
        Parameters:
        C - GenPolynomial
        A - GenPolynomial
        B - other GenPolynomial
        S - GenPolynomial
        T - GenPolynomial
        M - bound on the coefficients of A1 and B1 as factors of C.
        Returns:
        [A1,B1] = lift(C,A,B), with C = A1 * B1.
        Throws:
        NoLiftingException
      • liftHenselQuadratic

        public static <MOD extends GcdRingElem<MOD> & ModularHenselApprox<MOD> liftHenselQuadratic(GenPolynomial<BigInteger> C,                                                                            BigInteger M,                                                                            GenPolynomial<MOD> A,                                                                            GenPolynomial<MOD> B)                                                                               throws NoLiftingException
        Modular quadratic Hensel lifting algorithm on coefficients. Let p = A.ring.coFac.modul() = B.ring.coFac.modul() and assume C == A*B mod p with gcd(A,B) == 1 mod p. See algorithm 6.1. in Geddes et.al. and algorithms 3.5.{5,6} in Cohen. Quadratic version.
        Parameters:
        C - GenPolynomial
        A - GenPolynomial
        B - other GenPolynomial
        M - bound on the coefficients of A1 and B1 as factors of C.
        Returns:
        [A1,B1] = lift(C,A,B), with C = A1 * B1.
        Throws:
        NoLiftingException
      • liftHenselQuadraticFac

        public static <MOD extends GcdRingElem<MOD> & ModularHenselApprox<MOD> liftHenselQuadraticFac(GenPolynomial<BigInteger> C,                                                                               BigInteger M,                                                                               GenPolynomial<MOD> A,                                                                               GenPolynomial<MOD> B)                                                                                  throws NoLiftingException
        Modular Hensel lifting algorithm on coefficients. Let p = A.ring.coFac.modul() = B.ring.coFac.modul() and assume C == A*B mod p with gcd(A,B) == 1 mod p. See algorithm 6.1. in Geddes et.al. and algorithms 3.5.{5,6} in Cohen. Quadratic version.
        Parameters:
        C - GenPolynomial
        A - GenPolynomial
        B - other GenPolynomial
        M - bound on the coefficients of A1 and B1 as factors of C.
        Returns:
        [A1,B1] = lift(C,A,B), with C = A1 * B1.
        Throws:
        NoLiftingException
      • liftHenselQuadraticFac

        public static <MOD extends GcdRingElem<MOD> & ModularHenselApprox<MOD> liftHenselQuadraticFac(GenPolynomial<BigInteger> C,                                                                               BigInteger M,                                                                               GenPolynomial<MOD> A,                                                                               GenPolynomial<MOD> B,                                                                               GenPolynomial<MOD> S,                                                                               GenPolynomial<MOD> T)                                                                                  throws NoLiftingException
        Modular Hensel lifting algorithm on coefficients. Let p = A.ring.coFac.modul() = B.ring.coFac.modul() and assume C == A*B mod p with gcd(A,B) == 1 mod p and S A + T B == 1 mod p. See algorithm 6.1. in Geddes et.al. and algorithms 3.5.{5,6} in Cohen. Quadratic version, as it also lifts S A + T B == 1 mod p^{e+1}.
        Parameters:
        C - primitive GenPolynomial
        A - GenPolynomial
        B - other GenPolynomial
        S - GenPolynomial
        T - GenPolynomial
        M - bound on the coefficients of A1 and B1 as factors of C.
        Returns:
        [A1,B1] = lift(C,A,B), with C = A1 * B1.
        Throws:
        NoLiftingException
      • isHenselLift

        public static boolean isHenselLift(GenPolynomial<BigInteger> C,                   BigInteger M,                   BigInteger p,                   List<GenPolynomial<BigInteger>> G)
        Modular Hensel lifting test. Let p be a prime number and assume C == prod_{0,...,n-1} g_i mod p with gcd(g_i,g_j) == 1 mod p for i != j.
        Parameters:
        C - GenPolynomial
        G - = [g_0,...,g_{n-1}] list of GenPolynomial
        M - bound on the coefficients of g_i as factors of C.
        p - prime number.
        Returns:
        true if C = prod_{0,...,n-1} g_i mod p^e, else false.
      • isHenselLift

        public static boolean isHenselLift(GenPolynomial<BigInteger> C,                   BigInteger M,                   BigInteger p,                   GenPolynomial<BigInteger> A,                   GenPolynomial<BigInteger> B)
        Modular Hensel lifting test. Let p be a prime number and assume C == A * B mod p with gcd(A,B) == 1 mod p.
        Parameters:
        C - GenPolynomial
        A - GenPolynomial
        B - GenPolynomial
        M - bound on the coefficients of A and B as factors of C.
        p - prime number.
        Returns:
        true if C = A * B mod p**e, else false.
      • isHenselLift

        public static <MOD extends GcdRingElem<MOD> & Modular> boolean isHenselLift(GenPolynomial<BigInteger> C,                                                           BigInteger M,                                                           BigInteger p,                                                           HenselApprox<MOD> Ha)
        Modular Hensel lifting test. Let p be a prime number and assume C == A * B mod p with gcd(A,B) == 1 mod p.
        Parameters:
        C - GenPolynomial
        Ha - Hensel approximation.
        M - bound on the coefficients of A and B as factors of C.
        p - prime number.
        Returns:
        true if C = A * B mod p^e, else false.
      • liftExtendedEuclidean

        public static <MOD extends GcdRingElem<MOD> & ModularGenPolynomial<MOD>[] liftExtendedEuclidean(GenPolynomial<MOD> A,                                                                                 GenPolynomial<MOD> B,                                                                                 long k)                                                                                    throws NoLiftingException
        Constructing and lifting algorithm for extended Euclidean relation. Let p = A.ring.coFac.modul() and assume gcd(A,B) == 1 mod p.
        Parameters:
        A - modular GenPolynomial
        B - modular GenPolynomial
        k - desired approximation exponent p^k.
        Returns:
        [s,t] with s A + t B = 1 mod p^k.
        Throws:
        NoLiftingException
      • liftExtendedEuclidean

        public static <MOD extends GcdRingElem<MOD> & ModularList<GenPolynomial<MOD>> liftExtendedEuclidean(List<GenPolynomial<MOD>> A,                                                                                     long k)                                                                                        throws NoLiftingException
        Constructing and lifting algorithm for extended Euclidean relation. Let p = A_i.ring.coFac.modul() and assume gcd(A_i,A_j) == 1 mod p, i != j.
        Parameters:
        A - list of modular GenPolynomials
        k - desired approximation exponent p^k.
        Returns:
        [s_0,...,s_n-1] with sum_i s_i * B_i = 1 mod p^k, with B_i = prod_{i!=j} A_j.
        Throws:
        NoLiftingException
      • liftDiophant

        public static <MOD extends GcdRingElem<MOD> & ModularList<GenPolynomial<MOD>> liftDiophant(GenPolynomial<MOD> A,                                                                            GenPolynomial<MOD> B,                                                                            GenPolynomial<MOD> C,                                                                            long k)                                                                               throws NoLiftingException
        Modular diophantine equation solution and lifting algorithm. Let p = A_i.ring.coFac.modul() and assume gcd(A,B) == 1 mod p.
        Parameters:
        A - modular GenPolynomial, mod p^k
        B - modular GenPolynomial, mod p^k
        C - modular GenPolynomial, mod p^k
        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> & ModularList<GenPolynomial<MOD>> liftDiophant(List<GenPolynomial<MOD>> A,                                                                            GenPolynomial<MOD> C,                                                                            long k)                                                                               throws NoLiftingException
        Modular diophantine equation solution and lifting algorithm. Let p = A_i.ring.coFac.modul() and assume gcd(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
        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
      • liftDiophant

        public static <MOD extends GcdRingElem<MOD> & ModularList<GenPolynomial<MOD>> liftDiophant(GenPolynomial<MOD> A,                                                                            GenPolynomial<MOD> B,                                                                            long e,                                                                            long k)                                                                               throws NoLiftingException
        Modular diophantine equation solution and lifting algorithm. Let p = A_i.ring.coFac.modul() and assume gcd(A,B) == 1 mod p.
        Parameters:
        A - modular GenPolynomial
        B - modular GenPolynomial
        e - exponent for x^e
        k - desired approximation exponent p^k.
        Returns:
        [s, t] with s A' + t B' = x^e mod p^k, with A' = B, B' = A.
        Throws:
        NoLiftingException
      • liftDiophant

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

        public static <MOD extends GcdRingElem<MOD> & Modular> boolean isDiophantLift(GenPolynomial<MOD> A,                                                             GenPolynomial<MOD> B,                                                             GenPolynomial<MOD> S1,                                                             GenPolynomial<MOD> S2,                                                             GenPolynomial<MOD> C)
        Modular Diophant relation lifting test.
        Parameters:
        A - modular GenPolynomial
        B - modular GenPolynomial
        C - modular GenPolynomial
        S1 - modular GenPolynomial
        S2 - modular GenPolynomial
        Returns:
        true if A*S1 + B*S2 = C, else false.
      • isExtendedEuclideanLift

        public static <MOD extends GcdRingElem<MOD> & Modular> boolean isExtendedEuclideanLift(List<GenPolynomial<MOD>> A,                                                                      List<GenPolynomial<MOD>> S)
        Modular extended Euclidean relation lifting test.
        Parameters:
        A - list of GenPolynomials
        S - = [s_0,...,s_{n-1}] list of GenPolynomial
        Returns:
        true if prod_{0,...,n-1} s_i * B_i = 1 mod p^e, with B_i = prod_{i!=j} A_j, else false.
      • isDiophantLift

        public static <MOD extends GcdRingElem<MOD> & Modular> boolean isDiophantLift(List<GenPolynomial<MOD>> A,                                                             List<GenPolynomial<MOD>> S,                                                             GenPolynomial<MOD> C)
        Modular Diophant relation lifting test.
        Parameters:
        A - list of GenPolynomials
        S - = [s_0,...,s_{n-1}] list of GenPolynomials
        C - = GenPolynomial
        Returns:
        true if prod_{0,...,n-1} s_i * B_i = C mod p^k, with B_i = prod_{i!=j} A_j, else false.
      • liftHenselMonic

        public static <MOD extends GcdRingElem<MOD> & ModularList<GenPolynomial<MOD>> liftHenselMonic(GenPolynomial<BigInteger> C,                                                                               List<GenPolynomial<MOD>> F,                                                                               long k)                                                                                  throws NoLiftingException
        Modular Hensel lifting algorithm on coefficients. 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 - monic integer polynomial
        F - = [f_0,...,f_{n-1}] list of monic modular polynomials.
        k - approximation exponent.
        Returns:
        [g_0,...,g_{n-1}] with C = prod_{0,...,n-1} g_i mod p^k.
        Throws:
        NoLiftingException
      • liftHensel

        public static <MOD extends GcdRingElem<MOD> & ModularList<GenPolynomial<MOD>> liftHensel(GenPolynomial<BigInteger> C,                                                                          List<GenPolynomial<MOD>> F,                                                                          long k,                                                                          BigInteger g)                                                                             throws NoLiftingException
        Modular Hensel lifting algorithm on coefficients. 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
        F - = [f_0,...,f_{n-1}] list of monic modular polynomials.
        k - approximation exponent.
        g - leading coefficient.
        Returns:
        [g_0,...,g_{n-1}] with C = prod_{0,...,n-1} g_i mod p^k.
        Throws:
        NoLiftingException

SCaVis 1.8 © jWork.org