Class UnivariateGCD

• public final class UnivariateGCD
extends Object
Univariate polynomial GCD.
Since:
1.0
• Method Detail

• 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). 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)
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)