Package cc.redberry.rings.poly.univar

Class UnivariateGCD

java.lang.Object

cc.redberry.rings.poly.univar.UnivariateGCD

public final class UnivariateGCD
extends Object

Univariate polynomial GCD.

Since:

1.0

Method Summary

Modifier and Type	Method	Description
static <T extends IUnivariatePolynomial<T>> T[]	EuclidFirstBezoutCoefficient(T a, T b)	Returns array of [gcd(a,b), s] such that s * a + t * b = gcd(a, b)
static <T extends IUnivariatePolynomial<T>> T	EuclidGCD(T a, T b)	Returns the GCD calculated with Euclidean algorithm.
static <T extends IUnivariatePolynomial<T>> T[]	ExtendedEuclidGCD(T a, T b)	Runs extended Euclidean algorithm to compute [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b).
static <T extends IUnivariatePolynomial<T>> T[]	ExtendedHalfGCD(T a, T b)	Runs extended Half-GCD algorithm to compute [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b).
static <T extends IUnivariatePolynomial<T>> T	HalfGCD(T a, T b)	Half-GCD algorithm.
static UnivariatePolynomial<Rational<BigInteger>>[]	ModularExtendedRationalGCD(UnivariatePolynomial<Rational<BigInteger>> a, UnivariatePolynomial<Rational<BigInteger>> b)	Computes [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b).
static UnivariatePolynomial<Rational<BigInteger>>[]	ModularExtendedResultantGCDInQ(UnivariatePolynomial<Rational<BigInteger>> a, UnivariatePolynomial<Rational<BigInteger>> b)	Modular extended GCD algorithm for polynomials over Q with the use of resultants.
static UnivariatePolynomial<BigInteger>[]	ModularExtendedResultantGCDInZ(UnivariatePolynomial<BigInteger> a, UnivariatePolynomial<BigInteger> b)	Modular extended GCD algorithm for polynomials over Z with the use of resultants.
static UnivariatePolynomial<BigInteger>	ModularGCD(UnivariatePolynomial<BigInteger> a, UnivariatePolynomial<BigInteger> b)	Modular GCD algorithm for polynomials over Z.
static UnivariatePolynomialZ64	ModularGCD(UnivariatePolynomialZ64 a, UnivariatePolynomialZ64 b)	Modular GCD algorithm for polynomials over Z.
static <T extends IUnivariatePolynomial<T>> T[]	PolynomialExtendedGCD(T a, T b)	Computes [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b).
static <T extends IUnivariatePolynomial<T>> T[]	PolynomialFirstBezoutCoefficient(T a, T b)	Returns array of [gcd(a,b), s] such that s * a + t * b = gcd(a, b)
static <T extends IUnivariatePolynomial<T>> T	PolynomialGCD(Iterable<T> polynomials)	Returns GCD of a list of polynomials.
static <T extends IUnivariatePolynomial<T>> T	PolynomialGCD(T... polynomials)	Returns GCD of a list of polynomials.
static <T extends IUnivariatePolynomial<T>> T	PolynomialGCD(T a, T b)	Calculates the GCD of two polynomials.
static UnivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>>	PolynomialGCDInNumberField(UnivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> a, UnivariatePolynomial<UnivariatePolynomial<Rational<BigInteger>>> b)	Computes GCD via Langemyr & Mccallum modular algorithm over algebraic number field
static UnivariatePolynomial<UnivariatePolynomial<BigInteger>>	PolynomialGCDInRingOfIntegersOfNumberField(UnivariatePolynomial<UnivariatePolynomial<BigInteger>> a, UnivariatePolynomial<UnivariatePolynomial<BigInteger>> b)	Computes some GCD associate via Langemyr & Mccallum modular algorithm over algebraic integers
static boolean	updateCRT(ChineseRemainders.ChineseRemaindersMagic<BigInteger> magic, UnivariatePolynomial<BigInteger> accumulated, UnivariatePolynomialZp64 update)	Apply CRT to a poly

Methods inherited from class java.lang.Object

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

Method Details

PolynomialGCD

public static <T extends IUnivariatePolynomial<T>>
T PolynomialGCD(T a,
T b)

Calculates the GCD of two polynomials. Depending on the coefficient ring, the algorithm switches between Half-GCD (polys over finite fields), modular GCD (polys over Z and Q) and subresultant Euclid (other rings).

Parameters:

a - the first polynomial

b - the second polynomial

Returns:

GCD of two polynomials

PolynomialExtendedGCD

public static <T extends IUnivariatePolynomial<T>>
T[] PolynomialExtendedGCD(T a,
T b)

Computes [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b). Either resultant-based modular or Half-GCD algorithm is used.

Parameters:

a - the polynomial

b - the polynomial

Returns:

array of [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b) (gcd is monic)

See Also:

ExtendedHalfGCD(IUnivariatePolynomial, IUnivariatePolynomial)

PolynomialFirstBezoutCoefficient

public static <T extends IUnivariatePolynomial<T>>
T[] PolynomialFirstBezoutCoefficient(T a,
T b)

Returns array of [gcd(a,b), s] such that s * a + t * b = gcd(a, b)

Parameters:

a - the first poly for which the Bezout coefficient is computed

b - the second poly

Returns:

array of [gcd(a,b), s] such that s * a + t * b = gcd(a, b)

PolynomialGCD

public static <T extends IUnivariatePolynomial<T>>
T PolynomialGCD(T... polynomials)

Returns GCD of a list of polynomials.

Parameters:

polynomials - a set of polynomials

Returns:

GCD of polynomials

PolynomialGCD

public static <T extends IUnivariatePolynomial<T>>
T PolynomialGCD(Iterable<T> polynomials)

Returns GCD of a list of polynomials.

Parameters:

polynomials - a set of polynomials

Returns:

GCD of polynomials

EuclidGCD

public static <T extends IUnivariatePolynomial<T>>
T EuclidGCD(T a,
T b)

Returns the GCD calculated with Euclidean algorithm. If coefficient ring of the input is not a field (and thus polynomials does not form an integral ring), ArithmeticException may be thrown in case when some exact divisions are not possible.

Parameters:

a - poly

b - poly

Returns:

the GCD (monic if a and b are over field)

ExtendedEuclidGCD

public static <T extends IUnivariatePolynomial<T>>
T[] ExtendedEuclidGCD(T a,
T b)

Runs extended Euclidean algorithm to compute [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b). If coefficient ring of the input is not a field (and thus polynomials does not form an integral ring), ArithmeticException may be thrown in case when some exact divisions are not possible.

Parameters:

a - the polynomial

b - the polynomial

Returns:

array of [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b)

EuclidFirstBezoutCoefficient

public static <T extends IUnivariatePolynomial<T>>
T[] EuclidFirstBezoutCoefficient(T a,
T b)

Returns array of [gcd(a,b), s] such that s * a + t * b = gcd(a, b)

Parameters:

a - the first poly for which the Bezout coefficient is computed

b - the second poly

Returns:

array of [gcd(a,b), s] such that s * a + t * b = gcd(a, b)

HalfGCD

public static <T extends IUnivariatePolynomial<T>>
T HalfGCD(T a,
T b)

Half-GCD algorithm. The algorithm automatically switches to Euclidean algorithm for small input. If coefficient ring of the input is not a field (and thus polynomials does not form an integral ring), ArithmeticException may be thrown in case when some exact divisions are not possible.

Parameters:

a - poly

b - poly

Returns:

the GCD (monic)

ExtendedHalfGCD

public static <T extends IUnivariatePolynomial<T>>
T[] ExtendedHalfGCD(T a,
T b)

Runs extended Half-GCD algorithm to compute [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b). If coefficient ring of the input is not a field (and thus polynomials does not form an integral ring), ArithmeticException may be thrown in case when some exact divisions are not possible.

Parameters:

a - the polynomial

b - the polynomial

Returns:

array of [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b) (gcd is monic)

ModularGCD

public static UnivariatePolynomialZ64 ModularGCD(UnivariatePolynomialZ64 a,
UnivariatePolynomialZ64 b)

Modular GCD algorithm for polynomials over Z.

Parameters:

a - the first polynomial

b - the second polynomial

Returns:

GCD of two polynomials

ModularGCD

public static UnivariatePolynomial<BigInteger> ModularGCD(UnivariatePolynomial<BigInteger> a,
UnivariatePolynomial<BigInteger> b)

Modular GCD algorithm for polynomials over Z.

Parameters:

a - the first polynomial

b - the second polynomial

Returns:

GCD of two polynomials

ModularExtendedRationalGCD

public static UnivariatePolynomial<Rational<BigInteger>>[] ModularExtendedRationalGCD(UnivariatePolynomial<Rational<BigInteger>> a,
UnivariatePolynomial<Rational<BigInteger>> b)

Computes [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b).

Parameters:

a - the polynomial

b - the polynomial

Returns:

array of [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b) (gcd is monic)

See Also:

ExtendedHalfGCD(IUnivariatePolynomial, IUnivariatePolynomial)

ModularExtendedResultantGCDInQ

public static UnivariatePolynomial<Rational<BigInteger>>[] ModularExtendedResultantGCDInQ(UnivariatePolynomial<Rational<BigInteger>> a,
UnivariatePolynomial<Rational<BigInteger>> b)

Modular extended GCD algorithm for polynomials over Q with the use of resultants.

Returns:

array of [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b) (gcd is monic)

ModularExtendedResultantGCDInZ

public static UnivariatePolynomial<BigInteger>[] ModularExtendedResultantGCDInZ(UnivariatePolynomial<BigInteger> a,
UnivariatePolynomial<BigInteger> b)

Modular extended GCD algorithm for polynomials over Z with the use of resultants.

Returns:

array of [gcd(a,b), s, t] such that s * a + t * b = gcd(a, b) (gcd is monic)

PolynomialGCDInNumberField

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

Computes GCD via Langemyr & Mccallum modular algorithm over algebraic number field

PolynomialGCDInRingOfIntegersOfNumberField

public static UnivariatePolynomial<UnivariatePolynomial<BigInteger>> PolynomialGCDInRingOfIntegersOfNumberField(UnivariatePolynomial<UnivariatePolynomial<BigInteger>> a,
UnivariatePolynomial<UnivariatePolynomial<BigInteger>> b)

Computes some GCD associate via Langemyr & Mccallum modular algorithm over algebraic integers

updateCRT

public static boolean updateCRT(ChineseRemainders.ChineseRemaindersMagic<BigInteger> magic,
UnivariatePolynomial<BigInteger> accumulated,
UnivariatePolynomialZp64 update)

Apply CRT to a poly