cc.redberry.rings.poly.univar

## Class UnivariateGCD

• ```public final class UnivariateGCD
extends Object```
Univariate polynomial GCD.
Since:
1.0
• ### Method Summary

All Methods
Modifier and Type Method and 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)```
Modular GCD algorithm for polynomials over Z.
`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 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)
• #### 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)```
Modular GCD algorithm for polynomials over Z.
Parameters:
`a` - the first polynomial
`b` - the second polynomial
Returns:
GCD of two polynomials
• #### 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.
Parameters:
`a` - the first polynomial
`b` - the second polynomial
Returns:
GCD of two polynomials
• #### 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.
Parameters:
`a` - the first polynomial
`b` - the second polynomial
Returns:
GCD of two polynomials
• #### 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