edu.jas.ufd
Class HenselMultUtil

java.lang.Object
  edu.jas.ufd.HenselMultUtil

public class HenselMultUtil
extends java.lang.Object

Hensel multivariate lifting utilities.

Author:

Heinz Kredel

Constructor Summary

HenselMultUtil()

Method Summary

static <MOD extends GcdRingElem<MOD> & Modular> boolean	isHenselLift(GenPolynomial<BigInteger> C, GenPolynomial<MOD> Cp, java.util.List<GenPolynomial<MOD>> F, long k, java.util.List<GenPolynomial<MOD>> L) Modular Hensel lifting algorithm on coefficients test.
static <MOD extends GcdRingElem<MOD> & Modular> java.util.List<GenPolynomial<MOD>>	liftDiophant(GenPolynomial<MOD> A, GenPolynomial<MOD> B, GenPolynomial<MOD> C, java.util.List<MOD> V, long d, 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, java.util.List<MOD> V, long d, long k) Modular diophantine equation solution and lifting algorithm.
static <MOD extends GcdRingElem<MOD> & Modular> java.util.List<GenPolynomial<MOD>>	liftHensel(GenPolynomial<BigInteger> C, GenPolynomial<MOD> Cp, java.util.List<GenPolynomial<MOD>> F, java.util.List<MOD> V, long k, java.util.List<GenPolynomial<BigInteger>> G) Modular Hensel lifting algorithm.
static <MOD extends GcdRingElem<MOD> & Modular> java.util.List<GenPolynomial<MOD>>	liftHenselFull(GenPolynomial<BigInteger> C, java.util.List<GenPolynomial<MOD>> F, java.util.List<MOD> V, long k, java.util.List<GenPolynomial<BigInteger>> G) Modular Hensel full lifting algorithm.
static <MOD extends GcdRingElem<MOD> & Modular> java.util.List<GenPolynomial<MOD>>	liftHenselMonic(GenPolynomial<BigInteger> C, GenPolynomial<MOD> Cp, java.util.List<GenPolynomial<MOD>> F, java.util.List<MOD> V, long k) Modular Hensel lifting algorithm, monic case.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

HenselMultUtil

public HenselMultUtil()

Method Detail

liftDiophant

public static <MOD extends GcdRingElem<MOD> & Modular> java.util.List<GenPolynomial<MOD>> liftDiophant(GenPolynomial<MOD> A,
                                                                                                      GenPolynomial<MOD> B,
                                                                                                      GenPolynomial<MOD> C,
                                                                                                      java.util.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> java.util.List<GenPolynomial<MOD>> liftDiophant(java.util.List<GenPolynomial<MOD>> A,
                                                                                                      GenPolynomial<MOD> C,
                                                                                                      java.util.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,
                                                                           java.util.List<GenPolynomial<MOD>> F,
                                                                           long k,
                                                                           java.util.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.

k - approximation exponent.

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> java.util.List<GenPolynomial<MOD>> liftHenselMonic(GenPolynomial<BigInteger> C,
                                                                                                         GenPolynomial<MOD> Cp,
                                                                                                         java.util.List<GenPolynomial<MOD>> F,
                                                                                                         java.util.List<MOD> 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 substitution values, mod p^k

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> java.util.List<GenPolynomial<MOD>> liftHensel(GenPolynomial<BigInteger> C,
                                                                                                    GenPolynomial<MOD> Cp,
                                                                                                    java.util.List<GenPolynomial<MOD>> F,
                                                                                                    java.util.List<MOD> V,
                                                                                                    long k,
                                                                                                    java.util.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 substitution values, mod p^k

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> java.util.List<GenPolynomial<MOD>> liftHenselFull(GenPolynomial<BigInteger> C,
                                                                                                        java.util.List<GenPolynomial<MOD>> F,
                                                                                                        java.util.List<MOD> V,
                                                                                                        long k,
                                                                                                        java.util.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 substitution values, mod p^k

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