Package 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
Constructors Constructor Description HenselUtil()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static <MOD extends GcdRingElem<MOD> & Modular>
booleanisDiophantLift(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>
booleanisDiophantLift(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>
booleanisExtendedEuclideanLift(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>
booleanisHenselLift(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, long e, 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, 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>
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>
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.
-
-
-
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
- GenPolynomialA
- GenPolynomialB
- other GenPolynomialS
- GenPolynomialT
- GenPolynomialM
- 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
- GenPolynomialA
- GenPolynomialB
- other GenPolynomialM
- 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
- GenPolynomialA
- GenPolynomialB
- other GenPolynomialS
- GenPolynomialT
- GenPolynomialM
- 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
- GenPolynomialA
- GenPolynomialB
- other GenPolynomialM
- 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
- GenPolynomialA
- GenPolynomialB
- other GenPolynomialM
- 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 GenPolynomialA
- GenPolynomialB
- other GenPolynomialS
- GenPolynomialT
- GenPolynomialM
- 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
- GenPolynomialG
- = [g_0,...,g_{n-1}] list of GenPolynomialM
- 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
- GenPolynomialA
- GenPolynomialB
- GenPolynomialM
- 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
- GenPolynomialHa
- 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 GenPolynomialB
- modular GenPolynomialk
- 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 GenPolynomialsk
- 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^kB
- modular GenPolynomial, mod p^kC
- modular GenPolynomial, mod p^kk
- 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^kC
- modular GenPolynomial, mod p^kk
- 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 GenPolynomialB
- modular GenPolynomiale
- exponent for x^ek
- 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 GenPolynomialse
- exponent for x^ek
- 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 GenPolynomialB
- modular GenPolynomialC
- modular GenPolynomialS1
- modular GenPolynomialS2
- 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 GenPolynomialsS
- = [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 GenPolynomialsS
- = [s_0,...,s_{n-1}] list of GenPolynomialsC
- = 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 polynomialF
- = [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 polynomialF
- = [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
-
-