edu.jas.ufd
Class HenselUtil

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

public class HenselUtil
extends java.lang.Object

Hensel utilities for ufd.

Author:

Heinz Kredel

Constructor Summary

HenselUtil()

Method Summary

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

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> & 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