Package edu.jas.ufd
Class HenselMultUtil
java.lang.Object
edu.jas.ufd.HenselMultUtil
Hensel multivariate lifting utilities.
-
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionstatic <MOD extends GcdRingElem<MOD> & Modular>
booleanisHenselLift
(GenPolynomial<BigInteger> C, GenPolynomial<MOD> Cp, List<GenPolynomial<MOD>> F, List<GenPolynomial<MOD>> L) Modular Hensel lifting algorithm on coefficients test.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) Modular diophantine equation solution and lifting algorithm.static <MOD extends GcdRingElem<MOD> & Modular>
List<GenPolynomial<MOD>> liftDiophant
(List<GenPolynomial<MOD>> A, GenPolynomial<MOD> C, List<MOD> V, long d, long k) Modular diophantine equation solution and lifting algorithm.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) Modular Hensel lifting algorithm.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) Modular Hensel full lifting algorithm.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) Modular Hensel lifting algorithm, monic case.
-
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^kB
- modular GenPolynomial, mod p^kC
- modular GenPolynomial, mod p^kV
- list of substitution values, mod p^kd
- 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^kC
- modular GenPolynomial, mod p^kV
- list of substitution values, mod p^kd
- 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 polynomialCp
- GenPolynomial mod p^kF
- = [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 coefficientsCp
- GenPolynomial mod p^kF
- list of modular GenPolynomials, mod (I_v, p^k )V
- list of integer substitution valuesk
- 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 coefficientsCp
- GenPolynomial C mod p^kF
- list of modular GenPolynomials, mod (I_v, p^k )V
- list of integral substitution valuesk
- 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 coefficientsF
- list of modular GenPolynomials, mod (I_v, p )V
- list of integer substitution valuesk
- 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
-