Package 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
Constructors Constructor Description HenselMultUtil()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static <MOD extends GcdRingElem<MOD> & Modular>
booleanisHenselLift(GenPolynomial<BigInteger> C, GenPolynomial<MOD> Cp, java.util.List<GenPolynomial<MOD>> F, 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<BigInteger> 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<BigInteger> 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<BigInteger> V, long k)
Modular Hensel lifting algorithm, monic case.
-
-
-
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^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> 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^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, java.util.List<GenPolynomial<MOD>> F, 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 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> java.util.List<GenPolynomial<MOD>> liftHenselMonic(GenPolynomial<BigInteger> C, GenPolynomial<MOD> Cp, java.util.List<GenPolynomial<MOD>> F, java.util.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> java.util.List<GenPolynomial<MOD>> liftHensel(GenPolynomial<BigInteger> C, GenPolynomial<MOD> Cp, java.util.List<GenPolynomial<MOD>> F, java.util.List<BigInteger> 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 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> java.util.List<GenPolynomial<MOD>> liftHenselFull(GenPolynomial<BigInteger> C, java.util.List<GenPolynomial<MOD>> F, java.util.List<BigInteger> 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 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
-
-