Package cc.redberry.rings.poly.multivar

Class MultivariateGCD

java.lang.Object

cc.redberry.rings.poly.multivar.MultivariateGCD

public final class MultivariateGCD
extends Object

Multivariate polynomial GCD

Since:

1.0

Method Summary

Modifier and Type	Method	Description
static <E> MultivariatePolynomial<E>	BrownGCD(MultivariatePolynomial<E> a, MultivariatePolynomial<E> b)	Calculates GCD of two multivariate polynomials over Zp using Brown's algorithm with dense interpolation.
static MultivariatePolynomialZp64	BrownGCD(MultivariatePolynomialZp64 a, MultivariatePolynomialZp64 b)	Calculates GCD of two multivariate polynomials over Zp using Brown's algorithm with dense interpolation.
static <Term extends AMonomial<Term>, Poly extends AMultivariatePolynomial<Term, Poly>> Poly	EEZGCD(Poly a, Poly b)	Calculates GCD of two multivariate polynomials over Zp using enhanced EZ algorithm
static MultivariatePolynomialZp64	EZGCD(MultivariatePolynomialZp64 a, MultivariatePolynomialZp64 b)	Calculates GCD of two multivariate polynomials over Zp using EZ algorithm
static <E> MultivariatePolynomial<E>	KaltofenMonaganEEZModularGCDInGF(MultivariatePolynomial<E> a, MultivariatePolynomial<E> b)	Modular GCD algorithm for polynomials over finite fields of small cardinality.
static MultivariatePolynomialZp64	KaltofenMonaganEEZModularGCDInGF(MultivariatePolynomialZp64 a, MultivariatePolynomialZp64 b)	Modular GCD algorithm for polynomials over finite fields of small cardinality.
static MultivariatePolynomialZp64	KaltofenMonaganModularGCDInGF(MultivariatePolynomialZp64 a, MultivariatePolynomialZp64 b, cc.redberry.rings.poly.multivar.MultivariateGCD.KaltofenMonaganAlgorithm algorithm)	Modular GCD algorithm for polynomials over finite fields of small cardinality.
static <E> MultivariatePolynomial<E>	KaltofenMonaganSparseModularGCDInGF(MultivariatePolynomial<E> a, MultivariatePolynomial<E> b)	Modular GCD algorithm for polynomials over finite fields of small cardinality.
static MultivariatePolynomialZp64	KaltofenMonaganSparseModularGCDInGF(MultivariatePolynomialZp64 a, MultivariatePolynomialZp64 b)	Modular GCD algorithm for polynomials over finite fields of small cardinality.
static MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>>	ModularGCDInNumberFieldViaLangemyrMcCallum(MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> a, MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> b, BiFunction<MultivariatePolynomial<UnivariatePolynomialZp64>,MultivariatePolynomial<UnivariatePolynomialZp64>,MultivariatePolynomial<UnivariatePolynomialZp64>> modularAlgorithm)	Zippel's sparse modular interpolation algorithm for polynomials over simple field extensions with the use of Langemyr & McCallum approach to avoid rational reconstruction
static MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>>	ModularGCDInNumberFieldViaRationalReconstruction(MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> a, MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> b, BiFunction<MultivariatePolynomial<UnivariatePolynomialZp64>,MultivariatePolynomial<UnivariatePolynomialZp64>,MultivariatePolynomial<UnivariatePolynomialZp64>> modularAlgorithm)	Modular interpolation algorithm for polynomials over simple field extensions with the use of Langemyr & McCallum approach to avoid rational reconstruction
static MultivariatePolynomial<BigInteger>	ModularGCDInZ(MultivariatePolynomial<BigInteger> a, MultivariatePolynomial<BigInteger> b, BiFunction<MultivariatePolynomialZp64,MultivariatePolynomialZp64,MultivariatePolynomialZp64> gcdInZp)	Modular GCD algorithm for polynomials over Z.
static <Poly extends AMultivariatePolynomial> Poly	PolynomialGCD(Iterable<Poly> arr)	Calculates greatest common divisor of the array of polynomials
static <Poly extends AMultivariatePolynomial> Poly	PolynomialGCD(Poly... arr)	Calculates greatest common divisor of the array of polynomials
static <Poly extends AMultivariatePolynomial> Poly	PolynomialGCD(Poly a, Poly b)	Calculates greatest common divisor of two multivariate polynomials
static <Poly extends AMultivariatePolynomial> Poly	PolynomialGCDinGF(Poly a, Poly b)	Calculates greatest common divisor of two multivariate polynomials over finite fields
static MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>>	PolynomialGCDinNumberField(MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> a, MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> b)	Calculates greatest common divisor of two multivariate polynomials over Z
static MultivariatePolynomial<UnivariatePolynomial<BigInteger>>	PolynomialGCDinRingOfIntegersOfNumberField(MultivariatePolynomial<UnivariatePolynomial<BigInteger>> a, MultivariatePolynomial<UnivariatePolynomial<BigInteger>> b)	Calculates greatest common divisor of two multivariate polynomials over Z
static MultivariatePolynomial<BigInteger>	PolynomialGCDinZ(MultivariatePolynomial<BigInteger> a, MultivariatePolynomial<BigInteger> b)	Calculates greatest common divisor of two multivariate polynomials over Z
static <E> MultivariatePolynomial<E>	ZippelGCD(MultivariatePolynomial<E> a, MultivariatePolynomial<E> b)	Calculates GCD of two multivariate polynomials over Zp using Zippel's algorithm with sparse interpolation.
static MultivariatePolynomialZp64	ZippelGCD(MultivariatePolynomialZp64 a, MultivariatePolynomialZp64 b)	Calculates GCD of two multivariate polynomials over Zp using Zippel's algorithm with sparse interpolation.
static MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>>	ZippelGCDInNumberFieldViaLangemyrMcCallum(MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> a, MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> b)	Zippel's sparse modular interpolation algorithm for computing GCD associate for polynomials over simple field extensions with the use of Langemyr & McCallum approach to avoid rational reconstruction
static MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>>	ZippelGCDInNumberFieldViaRationalReconstruction(MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> a, MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> b)	Zippel's sparse modular interpolation algorithm for polynomials over simple field extensions with the use of rational reconstruction to reconstruct the result
static MultivariatePolynomial<BigInteger>	ZippelGCDInZ(MultivariatePolynomial<BigInteger> a, MultivariatePolynomial<BigInteger> b)	Sparse modular GCD algorithm for polynomials over Z.

Methods inherited from class java.lang.Object

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

Method Details

PolynomialGCD

public static <Poly extends AMultivariatePolynomial>
Poly PolynomialGCD(Poly... arr)

Calculates greatest common divisor of the array of polynomials

Parameters:

arr - set of polynomials

Returns:

the gcd

PolynomialGCD

public static <Poly extends AMultivariatePolynomial>
Poly PolynomialGCD(Iterable<Poly> arr)

Calculates greatest common divisor of the array of polynomials

Parameters:

arr - set of polynomials

Returns:

the gcd

PolynomialGCD

public static <Poly extends AMultivariatePolynomial>
Poly PolynomialGCD(Poly a,
Poly b)

Calculates greatest common divisor of two multivariate polynomials

Parameters:

a - the first poly

b - the second poly

Returns:

the gcd

PolynomialGCDinGF

public static <Poly extends AMultivariatePolynomial>
Poly PolynomialGCDinGF(Poly a,
Poly b)

Calculates greatest common divisor of two multivariate polynomials over finite fields

Parameters:

a - the first poly

b - the second poly

Returns:

the gcd

PolynomialGCDinZ

public static MultivariatePolynomial<BigInteger> PolynomialGCDinZ(MultivariatePolynomial<BigInteger> a,
MultivariatePolynomial<BigInteger> b)

Calculates greatest common divisor of two multivariate polynomials over Z

Parameters:

a - the first poly

b - the second poly

Returns:

the gcd

PolynomialGCDinNumberField

public static MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> PolynomialGCDinNumberField(MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> a,
MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> b)

Calculates greatest common divisor of two multivariate polynomials over Z

Parameters:

a - the first poly

b - the second poly

Returns:

the gcd

PolynomialGCDinRingOfIntegersOfNumberField

public static MultivariatePolynomial<UnivariatePolynomial<BigInteger>> PolynomialGCDinRingOfIntegersOfNumberField(MultivariatePolynomial<UnivariatePolynomial<BigInteger>> a,
MultivariatePolynomial<UnivariatePolynomial<BigInteger>> b)

Calculates greatest common divisor of two multivariate polynomials over Z

Parameters:

a - the first poly

b - the second poly

Returns:

the gcd

ZippelGCDInZ

public static MultivariatePolynomial<BigInteger> ZippelGCDInZ(MultivariatePolynomial<BigInteger> a,
MultivariatePolynomial<BigInteger> b)

Sparse modular GCD algorithm for polynomials over Z.

Parameters:

a - the first polynomial

b - the second polynomial

Returns:

GCD of two polynomials

ModularGCDInZ

public static MultivariatePolynomial<BigInteger> ModularGCDInZ(MultivariatePolynomial<BigInteger> a,
MultivariatePolynomial<BigInteger> b,
BiFunction<MultivariatePolynomialZp64,MultivariatePolynomialZp64,MultivariatePolynomialZp64> gcdInZp)

Modular GCD algorithm for polynomials over Z.

Parameters:

a - the first polynomial

b - the second polynomial

gcdInZp - algorithm for gcd in Zp

Returns:

GCD of two polynomials

ZippelGCDInNumberFieldViaRationalReconstruction

public static MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> ZippelGCDInNumberFieldViaRationalReconstruction(MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> a,
MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> b)

Zippel's sparse modular interpolation algorithm for polynomials over simple field extensions with the use of rational reconstruction to reconstruct the result

ZippelGCDInNumberFieldViaLangemyrMcCallum

public static MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> ZippelGCDInNumberFieldViaLangemyrMcCallum(MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> a,
MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> b)

Zippel's sparse modular interpolation algorithm for computing GCD associate for polynomials over simple field extensions with the use of Langemyr & McCallum approach to avoid rational reconstruction

ModularGCDInNumberFieldViaRationalReconstruction

public static MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> ModularGCDInNumberFieldViaRationalReconstruction(MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> a,
MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> b,
BiFunction<MultivariatePolynomial<UnivariatePolynomialZp64>,MultivariatePolynomial<UnivariatePolynomialZp64>,MultivariatePolynomial<UnivariatePolynomialZp64>> modularAlgorithm)

Modular interpolation algorithm for polynomials over simple field extensions with the use of Langemyr & McCallum approach to avoid rational reconstruction

ModularGCDInNumberFieldViaLangemyrMcCallum

public static MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> ModularGCDInNumberFieldViaLangemyrMcCallum(MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> a,
MultivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> b,
BiFunction<MultivariatePolynomial<UnivariatePolynomialZp64>,MultivariatePolynomial<UnivariatePolynomialZp64>,MultivariatePolynomial<UnivariatePolynomialZp64>> modularAlgorithm)

Zippel's sparse modular interpolation algorithm for polynomials over simple field extensions with the use of Langemyr & McCallum approach to avoid rational reconstruction

KaltofenMonaganSparseModularGCDInGF

public static <E> MultivariatePolynomial<E> KaltofenMonaganSparseModularGCDInGF(MultivariatePolynomial<E> a,
MultivariatePolynomial<E> b)

Modular GCD algorithm for polynomials over finite fields of small cardinality.

Parameters:

a - the first polynomial

b - the second polynomial

Returns:

GCD of two polynomials

KaltofenMonaganEEZModularGCDInGF

public static <E> MultivariatePolynomial<E> KaltofenMonaganEEZModularGCDInGF(MultivariatePolynomial<E> a,
MultivariatePolynomial<E> b)

Modular GCD algorithm for polynomials over finite fields of small cardinality.

Parameters:

a - the first polynomial

b - the second polynomial

Returns:

GCD of two polynomials

KaltofenMonaganSparseModularGCDInGF

public static MultivariatePolynomialZp64 KaltofenMonaganSparseModularGCDInGF(MultivariatePolynomialZp64 a,
MultivariatePolynomialZp64 b)

Modular GCD algorithm for polynomials over finite fields of small cardinality.

Parameters:

a - the first polynomial

b - the second polynomial

Returns:

GCD of two polynomials

KaltofenMonaganEEZModularGCDInGF

public static MultivariatePolynomialZp64 KaltofenMonaganEEZModularGCDInGF(MultivariatePolynomialZp64 a,
MultivariatePolynomialZp64 b)

Modular GCD algorithm for polynomials over finite fields of small cardinality.

Parameters:

a - the first polynomial

b - the second polynomial

Returns:

GCD of two polynomials

KaltofenMonaganModularGCDInGF

public static MultivariatePolynomialZp64 KaltofenMonaganModularGCDInGF(MultivariatePolynomialZp64 a,
MultivariatePolynomialZp64 b,
cc.redberry.rings.poly.multivar.MultivariateGCD.KaltofenMonaganAlgorithm algorithm)

Modular GCD algorithm for polynomials over finite fields of small cardinality.

Parameters:

a - the first polynomial

b - the second polynomial

algorithm - the actual algorithm

Returns:

GCD of two polynomials

BrownGCD

public static <E> MultivariatePolynomial<E> BrownGCD(MultivariatePolynomial<E> a,
MultivariatePolynomial<E> b)

Calculates GCD of two multivariate polynomials over Zp using Brown's algorithm with dense interpolation.

Parameters:

a - the first multivariate polynomial

b - the second multivariate polynomial

Returns:

greatest common divisor of a and b

ZippelGCD

public static <E> MultivariatePolynomial<E> ZippelGCD(MultivariatePolynomial<E> a,
MultivariatePolynomial<E> b)

Calculates GCD of two multivariate polynomials over Zp using Zippel's algorithm with sparse interpolation.

Parameters:

a - the first multivariate polynomial

b - the second multivariate polynomial

Returns:

greatest common divisor of a and b

BrownGCD

public static MultivariatePolynomialZp64 BrownGCD(MultivariatePolynomialZp64 a,
MultivariatePolynomialZp64 b)

Calculates GCD of two multivariate polynomials over Zp using Brown's algorithm with dense interpolation.

Parameters:

a - the first multivariate polynomial

b - the second multivariate polynomial

Returns:

greatest common divisor of a and b

ZippelGCD

public static MultivariatePolynomialZp64 ZippelGCD(MultivariatePolynomialZp64 a,
MultivariatePolynomialZp64 b)

Calculates GCD of two multivariate polynomials over Zp using Zippel's algorithm with sparse interpolation.

Parameters:

a - the first multivariate polynomial

b - the second multivariate polynomial

Returns:

greatest common divisor of a and b

EZGCD

public static MultivariatePolynomialZp64 EZGCD(MultivariatePolynomialZp64 a,
MultivariatePolynomialZp64 b)

Calculates GCD of two multivariate polynomials over Zp using EZ algorithm

Parameters:

a - the first multivariate polynomial

b - the second multivariate polynomial

Returns:

greatest common divisor of a and b

EEZGCD

public static <Term extends AMonomial<Term>,
Poly extends AMultivariatePolynomial<Term,
Poly>>
Poly EEZGCD(Poly a,
Poly b)

Calculates GCD of two multivariate polynomials over Zp using enhanced EZ algorithm

Parameters:

a - the first multivariate polynomial

b - the second multivariate polynomial

Returns:

greatest common divisor of a and b