HenselUtil

java.lang.Object
- edu.jas.ufd.HenselUtil

public class HenselUtil
extends java.lang.Object

Hensel utilities for ufd.

Author:: Heinz Kredel

Constructor Summary

Constructors
Constructor and Description

HenselUtil()

Constructors
Constructor and Description
`HenselUtil()`

Method Summary

All Methods Static Methods Concrete Methods
Modifier and Type	Method and Description
`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.
`static <MOD extends GcdRingElem<MOD> & Modular> boolean`	`isDiophantLift(java.util.List<GenPolynomial<MOD>> A, java.util.List<GenPolynomial<MOD>> S, GenPolynomial<MOD> C)` Modular Diophant relation lifting test.
`static <MOD extends GcdRingElem<MOD> & Modular> boolean`	`isExtendedEuclideanLift(java.util.List<GenPolynomial<MOD>> A, java.util.List<GenPolynomial<MOD>> S)` Modular extended Euclidean relation lifting test.
`static boolean`	`isHenselLift(GenPolynomial<BigInteger> C, BigInteger M, BigInteger p, GenPolynomial<BigInteger> A, GenPolynomial<BigInteger> B)` Modular Hensel lifting test.
`static <MOD extends GcdRingElem<MOD> & Modular> boolean`	`isHenselLift(GenPolynomial<BigInteger> C, BigInteger M, BigInteger p, HenselApprox<MOD> Ha)` Modular Hensel lifting test.
`static boolean`	`isHenselLift(GenPolynomial<BigInteger> C, BigInteger M, BigInteger p, java.util.List<GenPolynomial<BigInteger>> G)` Modular Hensel lifting test.
`static <MOD extends GcdRingElem<MOD> & Modular> java.util.List<GenPolynomial<MOD>>`	`liftDiophant(GenPolynomial<MOD> A, GenPolynomial<MOD> B, GenPolynomial<MOD> C, long k)` Modular diophantine equation solution and lifting algorithm.
`static <MOD extends GcdRingElem<MOD> & Modular> java.util.List<GenPolynomial<MOD>>`	`liftDiophant(GenPolynomial<MOD> A, GenPolynomial<MOD> B, long e, long k)` Modular diophantine equation solution and lifting algorithm.
`static <MOD extends GcdRingElem<MOD> & Modular> java.util.List<GenPolynomial<MOD>>`	`liftDiophant(java.util.List<GenPolynomial<MOD>> A, GenPolynomial<MOD> C, long k)` Modular diophantine equation solution and lifting algorithm.
`static <MOD extends GcdRingElem<MOD> & Modular> java.util.List<GenPolynomial<MOD>>`	`liftDiophant(java.util.List<GenPolynomial<MOD>> A, long e, long k)` Modular diophantine equation solution and lifting algorithm.
`static <MOD extends GcdRingElem<MOD> & Modular> GenPolynomial<MOD>[]`	`liftExtendedEuclidean(GenPolynomial<MOD> A, GenPolynomial<MOD> B, long k)` Constructing and lifting algorithm for extended Euclidean relation.
`static <MOD extends GcdRingElem<MOD> & Modular> java.util.List<GenPolynomial<MOD>>`	`liftExtendedEuclidean(java.util.List<GenPolynomial<MOD>> A, long k)` Constructing and lifting algorithm for extended Euclidean relation.
`static <MOD extends GcdRingElem<MOD> & Modular> HenselApprox<MOD>`	`liftHensel(GenPolynomial<BigInteger> C, BigInteger M, GenPolynomial<MOD> A, GenPolynomial<MOD> B)` Modular Hensel lifting algorithm on coefficients.
`static <MOD extends GcdRingElem<MOD> & Modular> HenselApprox<MOD>`	`liftHensel(GenPolynomial<BigInteger> C, BigInteger M, GenPolynomial<MOD> A, GenPolynomial<MOD> B, GenPolynomial<MOD> S, GenPolynomial<MOD> T)` Modular Hensel lifting algorithm on coefficients.
`static <MOD extends GcdRingElem<MOD> & Modular> java.util.List<GenPolynomial<MOD>>`	`liftHensel(GenPolynomial<BigInteger> C, java.util.List<GenPolynomial<MOD>> F, long k, BigInteger g)` Modular Hensel lifting algorithm on coefficients.
`static <MOD extends GcdRingElem<MOD> & Modular> java.util.List<GenPolynomial<MOD>>`	`liftHenselMonic(GenPolynomial<BigInteger> C, java.util.List<GenPolynomial<MOD>> F, long k)` Modular Hensel lifting algorithm on coefficients.
`static <MOD extends GcdRingElem<MOD> & Modular> HenselApprox<MOD>`	`liftHenselQuadratic(GenPolynomial<BigInteger> C, BigInteger M, GenPolynomial<MOD> A, GenPolynomial<MOD> B)` Modular quadratic Hensel lifting algorithm on coefficients.
`static <MOD extends GcdRingElem<MOD> & Modular> HenselApprox<MOD>`	`liftHenselQuadratic(GenPolynomial<BigInteger> C, BigInteger M, GenPolynomial<MOD> A, GenPolynomial<MOD> B, GenPolynomial<MOD> S, GenPolynomial<MOD> T)` Modular quadratic Hensel lifting algorithm on coefficients.
`static <MOD extends GcdRingElem<MOD> & Modular> HenselApprox<MOD>`	`liftHenselQuadraticFac(GenPolynomial<BigInteger> C, BigInteger M, GenPolynomial<MOD> A, GenPolynomial<MOD> B)` Modular Hensel lifting algorithm on coefficients.
`static <MOD extends GcdRingElem<MOD> & Modular> HenselApprox<MOD>`	`liftHenselQuadraticFac(GenPolynomial<BigInteger> C, BigInteger M, GenPolynomial<MOD> A, GenPolynomial<MOD> B, GenPolynomial<MOD> S, GenPolynomial<MOD> T)` Modular Hensel lifting algorithm on coefficients.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail
- HenselUtil
```
public HenselUtil()
```

Method Detail

liftHensel

public static <MOD extends GcdRingElem<MOD> & Modular> HenselApprox<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> & Modular> HenselApprox<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> & Modular> HenselApprox<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> & Modular> HenselApprox<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> & Modular> HenselApprox<MOD> liftHenselQuadraticFac(GenPolynomial<BigInteger> C,
                                                                                                BigInteger M,
                                                                                                GenPolynomial<MOD> A,
                                                                                                GenPolynomial<MOD> B)
                                                                                         throws NoLiftingException

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> & Modular> HenselApprox<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,
                                   java.util.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> & Modular> GenPolynomial<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> & Modular> java.util.List<GenPolynomial<MOD>> liftExtendedEuclidean(java.util.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> & Modular> java.util.List<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> & Modular> java.util.List<GenPolynomial<MOD>> liftDiophant(java.util.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> & Modular> java.util.List<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> & Modular> java.util.List<GenPolynomial<MOD>> liftDiophant(java.util.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(java.util.List<GenPolynomial<MOD>> A,
                                                                                       java.util.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(java.util.List<GenPolynomial<MOD>> A,
                                                                              java.util.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> & Modular> java.util.List<GenPolynomial<MOD>> liftHenselMonic(GenPolynomial<BigInteger> C,
                                                                                                          java.util.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> & Modular> java.util.List<GenPolynomial<MOD>> liftHensel(GenPolynomial<BigInteger> C,
                                                                                                     java.util.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

Class HenselUtil

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

HenselUtil

Method Detail

liftHensel

liftHensel

liftHenselQuadratic

liftHenselQuadratic

liftHenselQuadraticFac

liftHenselQuadraticFac

isHenselLift

isHenselLift

isHenselLift

liftExtendedEuclidean

liftExtendedEuclidean

liftDiophant

liftDiophant

liftDiophant

liftDiophant

isDiophantLift

isExtendedEuclideanLift

isDiophantLift

liftHenselMonic

liftHensel