Package cc.redberry.rings.poly.univar

Class HenselLifting

java.lang.Object

cc.redberry.rings.poly.univar.HenselLifting

public final class HenselLifting
extends Object

Methods for univariate Hensel lifting.

Implementation notes. Two methods for Hensel lift are implemented: quadratic and linear. For N iterations quadratic lift will lift to p^{2^N} while linear just to p^N. While quadratic lift converges much faster, it works with BigIntegers in all intermediate steps, so each step is quite expensive. Linear lift is implemented so that it starts with machine-word modulus, and perform all hard intermediate calculations with machine-word arithmetic, converting to BigIntegers only a few times. In this way, a single step of linear lift is very cheap, but the convergence is worse. The actual lifting used in factorization switches between linear and quadratic lift in order to obtain the best trade-off. NOTE: Quadratic lifts may fail in Z/2

Since:

1.0

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	HenselLifting.bLinearLift	Linear Hensel lift for BigIntegers arithmetics.
static class	HenselLifting.bQuadraticLift	Quadratic Hensel lift for BigIntegers arithmetics.
static interface	HenselLifting.LiftableQuintet<PolyZp extends IUnivariatePolynomial<PolyZp>>	Liftable quintet.
static class	HenselLifting.lLinearLift	Linear Hensel lift for machine word arithmetics.
static class	HenselLifting.lQuadraticLift	Quadratic Hensel lift for machine word arithmetics.

Method Summary

Modifier and Type	Method	Description
static HenselLifting.bLinearLift	createLinearLift(long modulus, UnivariatePolynomial<BigInteger> poly, UnivariatePolynomialZp64 aFactor, UnivariatePolynomialZp64 bFactor)	Creates linear Hensel lift.
static HenselLifting.lLinearLift	createLinearLift(long modulus, UnivariatePolynomialZ64 poly, UnivariatePolynomialZp64 aFactor, UnivariatePolynomialZp64 bFactor)	Creates linear Hensel lift.
static HenselLifting.bLinearLift	createLinearLift(BigInteger modulus, UnivariatePolynomial<BigInteger> poly, UnivariatePolynomialZp64 aFactor, UnivariatePolynomialZp64 bFactor)	Creates linear Hensel lift.
static HenselLifting.lLinearLift	createLinearLift(BigInteger modulus, UnivariatePolynomialZ64 poly, UnivariatePolynomialZp64 aFactor, UnivariatePolynomialZp64 bFactor)	Creates linear Hensel lift.
static HenselLifting.lQuadraticLift	createQuadraticLift(long modulus, UnivariatePolynomialZ64 poly, UnivariatePolynomialZp64 aFactor, UnivariatePolynomialZp64 bFactor)	Creates quadratic Hensel lift.
static HenselLifting.bQuadraticLift	createQuadraticLift(BigInteger modulus, UnivariatePolynomial<BigInteger> poly, UnivariatePolynomial<BigInteger> aFactor, UnivariatePolynomial<BigInteger> bFactor)	Creates quadratic Hensel lift.
static HenselLifting.bQuadraticLift	createQuadraticLift(BigInteger modulus, UnivariatePolynomial<BigInteger> poly, UnivariatePolynomialZp64 aFactor, UnivariatePolynomialZp64 bFactor)	Creates quadratic Hensel lift.
static List<UnivariatePolynomialZp64>	liftFactorization(long modulus, long finalModulus, int nIterations, UnivariatePolynomialZ64 poly, List<UnivariatePolynomialZp64> modularFactors, boolean quadratic)	Lifts modular factorization nIterations times using whether linear or quadratic lifting.
static List<UnivariatePolynomialZp64>	liftFactorization(long modulus, long desiredBound, UnivariatePolynomialZ64 poly, List<UnivariatePolynomialZp64> modularFactors, boolean quadratic)	Lifts modular factorization until modulus will overcome desiredBound.
static List<UnivariatePolynomial<BigInteger>>	liftFactorization(BigInteger modulus, BigInteger desiredBound, UnivariatePolynomial<BigInteger> poly, List<UnivariatePolynomialZp64> modularFactors)	Lifts modular factorization until modulus will overcome desiredBound.
static List<UnivariatePolynomial<BigInteger>>	liftFactorization(BigInteger modulus, BigInteger desiredBound, UnivariatePolynomial<BigInteger> poly, List<UnivariatePolynomialZp64> modularFactors, boolean quadratic)	Lifts modular factorization until modulus will overcome desiredBound.
static List<UnivariatePolynomial<BigInteger>>	liftFactorizationQuadratic(BigInteger modulus, BigInteger desiredBound, UnivariatePolynomial<BigInteger> poly, List<UnivariatePolynomial<BigInteger>> modularFactors)	Lifts modular factorization until modulus will overcome desiredBound.

Methods inherited from class java.lang.Object

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

Method Detail

createQuadraticLift

public static HenselLifting.lQuadraticLift createQuadraticLift(long modulus,
                                                               UnivariatePolynomialZ64 poly,
                                                               UnivariatePolynomialZp64 aFactor,
                                                               UnivariatePolynomialZp64 bFactor)

Creates quadratic Hensel lift.

Parameters:

modulus - the initial modulus

poly - Z[x] polynomial

aFactor - first factor of poly that poly = aFactor * bFactor mod modulus

bFactor - second factor of poly that poly = aFactor * bFactor mod modulus

Returns:

quadratic Hensel lift

createQuadraticLift

public static HenselLifting.bQuadraticLift createQuadraticLift(BigInteger modulus,
                                                               UnivariatePolynomial<BigInteger> poly,
                                                               UnivariatePolynomial<BigInteger> aFactor,
                                                               UnivariatePolynomial<BigInteger> bFactor)

Creates quadratic Hensel lift.

Parameters:

modulus - the initial modulus

poly - Z[x] polynomial

aFactor - first factor of poly that poly = aFactor * bFactor mod modulus

bFactor - second factor of poly that poly = aFactor * bFactor mod modulus

Returns:

quadratic Hensel lift

createQuadraticLift

public static HenselLifting.bQuadraticLift createQuadraticLift(BigInteger modulus,
                                                               UnivariatePolynomial<BigInteger> poly,
                                                               UnivariatePolynomialZp64 aFactor,
                                                               UnivariatePolynomialZp64 bFactor)

Creates quadratic Hensel lift.

Parameters:

modulus - the initial modulus

poly - Z[x] polynomial

aFactor - first factor of poly that poly = aFactor * bFactor mod modulus

bFactor - second factor of poly that poly = aFactor * bFactor mod modulus

Returns:

quadratic Hensel lift

createLinearLift

public static HenselLifting.lLinearLift createLinearLift(BigInteger modulus,
                                                         UnivariatePolynomialZ64 poly,
                                                         UnivariatePolynomialZp64 aFactor,
                                                         UnivariatePolynomialZp64 bFactor)

Creates linear Hensel lift.

Parameters:

modulus - the initial modulus

poly - Z[x] polynomial

aFactor - first factor of poly that poly = aFactor * bFactor mod modulus

bFactor - second factor of poly that poly = aFactor * bFactor mod modulus

Returns:

linear Hensel lift

createLinearLift

public static HenselLifting.bLinearLift createLinearLift(BigInteger modulus,
                                                         UnivariatePolynomial<BigInteger> poly,
                                                         UnivariatePolynomialZp64 aFactor,
                                                         UnivariatePolynomialZp64 bFactor)

Creates linear Hensel lift.

Parameters:

modulus - the initial modulus

poly - Z[x] polynomial

aFactor - first factor of poly that poly = aFactor * bFactor mod modulus

bFactor - second factor of poly that poly = aFactor * bFactor mod modulus

Returns:

linear Hensel lift

createLinearLift

public static HenselLifting.lLinearLift createLinearLift(long modulus,
                                                         UnivariatePolynomialZ64 poly,
                                                         UnivariatePolynomialZp64 aFactor,
                                                         UnivariatePolynomialZp64 bFactor)

Creates linear Hensel lift.

Parameters:

modulus - the initial modulus

poly - Z[x] polynomial

aFactor - first factor of poly that poly = aFactor * bFactor mod modulus

bFactor - second factor of poly that poly = aFactor * bFactor mod modulus

Returns:

linear Hensel lift

createLinearLift

public static HenselLifting.bLinearLift createLinearLift(long modulus,
                                                         UnivariatePolynomial<BigInteger> poly,
                                                         UnivariatePolynomialZp64 aFactor,
                                                         UnivariatePolynomialZp64 bFactor)

Creates linear Hensel lift.

Parameters:

modulus - the initial modulus

poly - Z[x] polynomial

aFactor - first factor of poly that poly = aFactor * bFactor mod modulus

bFactor - second factor of poly that poly = aFactor * bFactor mod modulus

Returns:

linear Hensel lift

liftFactorization

public static List<UnivariatePolynomialZp64> liftFactorization(long modulus,
                                                               long desiredBound,
                                                               UnivariatePolynomialZ64 poly,
                                                               List<UnivariatePolynomialZp64> modularFactors,
                                                               boolean quadratic)

Lifts modular factorization until modulus will overcome desiredBound.

Parameters:

modulus - initial modulus so that modularFactors are true factors of poly mod modulus

desiredBound - desired modulus

poly - initial Z[x] polynomial

modularFactors - factorization of poly.modulus(modulus)

quadratic - whether to use quadratic of linear lift

Returns:

factorization of poly.modulus(finalModulus) with some finalModulus greater than desiredBound

liftFactorization

public static List<UnivariatePolynomialZp64> liftFactorization(long modulus,
                                                               long finalModulus,
                                                               int nIterations,
                                                               UnivariatePolynomialZ64 poly,
                                                               List<UnivariatePolynomialZp64> modularFactors,
                                                               boolean quadratic)

Lifts modular factorization nIterations times using whether linear or quadratic lifting.

Parameters:

modulus - initial modulus so that modularFactors are true factors of poly mod modulus

finalModulus - final modulus that will be obtained after lifting

nIterations - number of lifting steps to do

poly - initial Z[x] polynomial

modularFactors - factorization of poly.modulus(modulus)

quadratic - whether to use quadratic of linear lift

Returns:

factorization of poly.modulus(finalModulus)

liftFactorization

public static List<UnivariatePolynomial<BigInteger>> liftFactorization(BigInteger modulus,
                                                                       BigInteger desiredBound,
                                                                       UnivariatePolynomial<BigInteger> poly,
                                                                       List<UnivariatePolynomialZp64> modularFactors,
                                                                       boolean quadratic)

Lifts modular factorization until modulus will overcome desiredBound. Note: if quadratic == false modulus must fit 64-bit.

Parameters:

modulus - initial modulus so that modularFactors are true factors of poly mod modulus

desiredBound - desired modulus

poly - initial Z[x] polynomial

modularFactors - factorization of poly.modulus(modulus)

quadratic - whether to use quadratic of linear lift

Returns:

factorization of poly.modulus(finalModulus) with some finalModulus greater than desiredBound

liftFactorizationQuadratic

public static List<UnivariatePolynomial<BigInteger>> liftFactorizationQuadratic(BigInteger modulus,
                                                                                BigInteger desiredBound,
                                                                                UnivariatePolynomial<BigInteger> poly,
                                                                                List<UnivariatePolynomial<BigInteger>> modularFactors)

Lifts modular factorization until modulus will overcome desiredBound.

Parameters:

modulus - initial modulus so that modularFactors are true factors of poly mod modulus

desiredBound - desired modulus

poly - initial Z[x] polynomial

modularFactors - factorization of poly.modulus(modulus)

Returns:

factorization of poly.modulus(finalModulus) with some finalModulus greater than desiredBound

liftFactorization

public static List<UnivariatePolynomial<BigInteger>> liftFactorization(BigInteger modulus,
                                                                       BigInteger desiredBound,
                                                                       UnivariatePolynomial<BigInteger> poly,
                                                                       List<UnivariatePolynomialZp64> modularFactors)

Lifts modular factorization until modulus will overcome desiredBound. Implementation note: method will switch between linear and quadratic lift depending on the required lifting iterations.

Parameters:

modulus - initial modulus so that modularFactors are true factors of poly mod modulus

desiredBound - desired modulus

poly - initial Z[x] polynomial

modularFactors - factorization of poly.modulus(modulus)

Returns:

factorization of poly.modulus(finalModulus) with some finalModulus greater than desiredBound