The mathIT Library
A Java™ API for mathematics
org.mathIT.algebra

## Class PolynomialZ

• All Implemented Interfaces:
Serializable, Cloneable, Map<BigInteger,BigInteger>, NavigableMap<BigInteger,BigInteger>, SortedMap<BigInteger,BigInteger>

```public class PolynomialZ
extends TreeMap<BigInteger,BigInteger>```
This class enables to generate objects representing polynomials with integer coefficients. A polynomial with integer coefficients has the form

p(x)   =   a0 + a1 x + a2 x2 +   ...   + an xn

where a0, a1, ..., an, and an ǂ 0. Then n is called the degree of the polynomial. Internally, a polynomial is represented by a sorted map, where the key represents the unique exponent and the value the respective coefficient, i.e., is given by the map

[<n,an>, ..., <0,a0>]

The default comparator for the exponents, i.e., the keys of this TreeMap, is `BigExponentComparator`, with a descending order. The simplest way to create a polynomial is given by the following code snippet:
```     PolynomialZ p = new PolynomialZ();
p.put( new BigInteger("1023"), new BigInteger("1") );
p.put( new BigInteger("2"), new BigInteger("-3") );
p.put( new BigInteger("1"), new BigInteger("5") );
p.put( new BigInteger("0"), new BigInteger("-1") );
```
Here the order of put instructions is arbitrary. This object then represents the polynomial

p(x)   =   x1023 - 3x2 + 5x - 1

This class requires JDK 5 or higher.
Version:
1.1
Author:
Andreas de Vries
`Polynomial`, Serialized Form

• ### Nested classes/interfaces inherited from class java.util.AbstractMap

`AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>`
• ### Method Summary

All Methods
Modifier and Type Method and Description
`PolynomialZ[]` `divide(PolynomialZ v)`
Divides this polynomial by the given polynomial v and returns an array {q,r} holding the quotient q as the first entry and the remainder r as the second entry.
`PolynomialZ[]` ```divideMod(PolynomialZ v, BigInteger m)```
Divides this polynomial by the given polynomial v modulo m and returns an array {q,r} holding the quotient q as the first entry and the remainder r as the second entry.
`BigInteger` `evaluate(BigInteger x)`
Evaluates this polynomial at the point x.
`BigInteger` ```evaluateMod(BigInteger x, BigInteger n)```
Evaluates this polynomial at the point x modulo n.
`BigInteger` `getDegree()`
Returns the degree of this polynomial.
`PolynomialZ` `minus(PolynomialZ q)`
Returns the difference this - q of this polynomial and the specified polynomial q.
`PolynomialZ` ```minus(PolynomialZ q, BigInteger m)```
Returns the difference this - q of this polynomial and the specified polynomial q, with coefficients modula m.
`PolynomialZ` `mod(PolynomialZ y)`
Returns the remainder of the division of this polynomial by the given polynomial y.
`PolynomialZ` ```mod(PolynomialZ y, BigInteger m)```
Returns the remainder of the division of this polynomial by the given polynomial y modulo m.
`PolynomialZ` ```modPow(BigInteger e, int r, BigInteger n)```
Returns se mod (xr - 1, n) where s is this polynomial.
`PolynomialZ` ```modPow(int e, BigInteger n)```
Returns the polynomial qe mod (p, n) where q is this polynomial.
`PolynomialZ` ```modPow(PolynomialZ p, BigInteger e, BigInteger n)```
Returns the polynomial qe mod (p, n) where q is this polynomial.
`PolynomialZ` `multiply(PolynomialZ q)`
Multiplies this polynomial with the given polynomial q.
`PolynomialZ` ```multiplyMod(PolynomialZ q, BigInteger n)```
Multiplies this polynomial with the given polynomial q modulo n.
`PolynomialZ` ```multiplyMod2(PolynomialZ q, BigInteger n)```
Multiplies this polynomial with the given polynomial q modulo n.
`PolynomialZ` `plus(PolynomialZ q)`
Returns the sum this + q of this polynomial and the specified polynomial q.
`PolynomialZ` ```plus(PolynomialZ q, BigInteger m)```
Returns the sum this + q of this polynomial and the specified polynomial q, with coefficients modulo m.
`BigInteger` ```put(BigInteger exponent, BigInteger coefficient)```
Adds the term ae xe to this polynomial.
`String` `toBinaryString()`
Returns a binary string representation of this polynomial, where the j-the bit (counted from the right) is zero iff the coefficient of xj is zero.
`String` `toHTMLString()`
Returns a HTML string representation of this polynomial.
`String` `toString()`
Returns a string representation of this polynomial.
• ### Methods inherited from class java.util.TreeMap

`ceilingEntry, ceilingKey, clear, clone, comparator, containsKey, containsValue, descendingKeySet, descendingMap, entrySet, firstEntry, firstKey, floorEntry, floorKey, forEach, get, headMap, headMap, higherEntry, higherKey, keySet, lastEntry, lastKey, lowerEntry, lowerKey, navigableKeySet, pollFirstEntry, pollLastEntry, putAll, remove, replace, replace, replaceAll, size, subMap, subMap, tailMap, tailMap, values`
• ### Methods inherited from class java.util.AbstractMap

`equals, hashCode, isEmpty`
• ### Methods inherited from class java.lang.Object

`finalize, getClass, notify, notifyAll, wait, wait, wait`
• ### Methods inherited from interface java.util.Map

`compute, computeIfAbsent, computeIfPresent, equals, getOrDefault, hashCode, isEmpty, merge, putIfAbsent, remove`
• ### Constructor Detail

• #### PolynomialZ

`public PolynomialZ(BigExponentComparator ec)`
Creates an empty polynomial with the given `BigExponentComparator`.
Parameters:
`ec` - an exponent comparator
• #### PolynomialZ

```public PolynomialZ(BigInteger exponent,
BigInteger coefficient)```
Creates a polynomial with a the single term ae xe and a new `BigExponentComparator`.
Parameters:
`exponent` - the exponent e
`coefficient` - the coefficient ae
• #### PolynomialZ

```public PolynomialZ(BigInteger exponent,
BigInteger coefficient,
BigExponentComparator ec)```
Creates a polynomial with a the single term ae xe and the given `BigExponentComparator`.
Parameters:
`exponent` - the exponent e
`coefficient` - the coefficient ae
`ec` - the comparator to compare exponents
• ### Method Detail

• #### put

```public BigInteger put(BigInteger exponent,
BigInteger coefficient)```
Adds the term ae xe to this polynomial. Here ae may be negative, whereas e must be a non-negative integer.
Specified by:
`put` in interface `Map<BigInteger,BigInteger>`
Overrides:
`put` in class `TreeMap<BigInteger,BigInteger>`
Parameters:
`exponent` - the exponent e in the term ae xe
`coefficient` - the coefficient ae in the term ae xe
Returns:
the previous coefficient associated with the exponent, or null if there does not exist a term with the exponent e in the polynomial.
• #### plus

`public PolynomialZ plus(PolynomialZ q)`
Returns the sum this + q of this polynomial and the specified polynomial q.
Parameters:
`q` - the polynomial to be added to this polynomial
Returns:
the sum this + q
• #### plus

```public PolynomialZ plus(PolynomialZ q,
BigInteger m)```
Returns the sum this + q of this polynomial and the specified polynomial q, with coefficients modulo m.
Parameters:
`q` - the polynomial to be added to this polynomial
`m` - the summand
Returns:
the sum this + q
• #### minus

`public PolynomialZ minus(PolynomialZ q)`
Returns the difference this - q of this polynomial and the specified polynomial q.
Parameters:
`q` - the polynomial to be subtracted from this polynomial
Returns:
the difference this - q
• #### minus

```public PolynomialZ minus(PolynomialZ q,
BigInteger m)```
Returns the difference this - q of this polynomial and the specified polynomial q, with coefficients modula m.
Parameters:
`q` - the polynomial to be subtracted from this polynomial
`m` - the modulus
Returns:
the difference this - q
• #### multiply

`public PolynomialZ multiply(PolynomialZ q)`
Multiplies this polynomial with the given polynomial q.
Parameters:
`q` - the polynomial to be multiplied with this polynomial
Returns:
the product of this polynomial times q
• #### multiplyMod

```public PolynomialZ multiplyMod(PolynomialZ q,
BigInteger n)```
Multiplies this polynomial with the given polynomial q modulo n. This means that all coefficients of the involved polynomials are computed modulo n.
Parameters:
`q` - the polynomial to be multiplied with this polynomial
`n` - the modulus
Returns:
the product of this polynomial times q, with coefficients mod n
• #### multiplyMod2

```public PolynomialZ multiplyMod2(PolynomialZ q,
BigInteger n)```
Multiplies this polynomial with the given polynomial q modulo n. This means that all coefficients of the involved polynomials are computed modulo n. This methods is implemented to walk through all possible powers of the two involved polynomials; in consequence it should be faster than `multiplyMod(PolynomialZ, BigInteger)` if all, or nearly all, powers have non-vanishing coefficients.
Parameters:
`q` - the polynomial to be multiplied with this polynomial
`n` - the modulus
Returns:
the product of this polynomial times q, with coefficients mod n
`multiplyMod(PolynomialZ, BigInteger)`
• #### divide

`public PolynomialZ[] divide(PolynomialZ v)`
Divides this polynomial by the given polynomial v and returns an array {q,r} holding the quotient q as the first entry and the remainder r as the second entry.
Parameters:
`v` - the polynomial to divide this polynomial
Returns:
the array {q,r} where q is the quotient of this polynomial, say u, over v, and r is the remainder polynomial such that u = qv + r
• #### mod

`public PolynomialZ mod(PolynomialZ y)`
Returns the remainder of the division of this polynomial by the given polynomial y. The algorithm is implemented after R. Crandall & C. Pomerance: Prime Numbers. A Computational Perspective. 2nd edition. Springer, New York 2005, &sec;9.6.2
Parameters:
`y` - the polynomial to divide this polynomial
Returns:
the remainder r, which is the unique polynomial with coefficients mod m such that u = qv + r mod m, where u is this polynomial and q is the quotient u/v
• #### mod

```public PolynomialZ mod(PolynomialZ y,
BigInteger m)```
Returns the remainder of the division of this polynomial by the given polynomial y modulo m. Modulo means that all coefficients of the involved polynomials are computed modulo m. The algorithm is implemented after R. Crandall & C. Pomerance: Prime Numbers. A Computational Perspective. 2nd edition. Springer, New York 2005, &sec;9.6.2
Parameters:
`y` - the polynomial to divide this polynomial
`m` - the modulus
Returns:
the remainder r, which is the unique polynomial with coefficients mod m such that u = qv + r mod m, where u is this polynomial and q is the quotient u/v
• #### divideMod

```public PolynomialZ[] divideMod(PolynomialZ v,
BigInteger m)```
Divides this polynomial by the given polynomial v modulo m and returns an array {q,r} holding the quotient q as the first entry and the remainder r as the second entry. Modulo means that all coefficients of the involved polynomials are computed modulo m.
Parameters:
`v` - the polynomial to divide this polynomial
`m` - the modulus
Returns:
the array {q,r} where q is the quotient of this polynomial, say u, over v, and r is the remainder polynomial such that u = qv + r mod m
• #### modPow

```public PolynomialZ modPow(int e,
BigInteger n)```
Returns the polynomial qe mod (p, n) where q is this polynomial.
Parameters:
`e` - the exponent
`n` - the modulus
Returns:
`this`e mod n
• #### modPow

```public PolynomialZ modPow(PolynomialZ p,
BigInteger e,
BigInteger n)```
Returns the polynomial qe mod (p, n) where q is this polynomial. Naive algorithm.
Parameters:
`p` - the modulus polynomial
`e` - the exponent
`n` - the modulus
Returns:
`this`e mod (p, n)
• #### modPow

```public PolynomialZ modPow(BigInteger e,
int r,
BigInteger n)```
Returns se mod (xr - 1, n) where s is this polynomial.
Parameters:
`e` - the exponent
`r` - the degree of the monic polynomial xr - 1
`n` - the modulus
Returns:
se mod (xr - 1, n) where s is this polynomial
Throws:
`IllegalArgumentException` - if r \$lt; 0
• #### evaluate

`public BigInteger evaluate(BigInteger x)`
Evaluates this polynomial at the point x. The algorithm is naive and does not use the Horner scheme.
Parameters:
`x` - the argument value to be evaluated
Returns:
the value of s(x) mod n, where s is this polynomial
• #### evaluateMod

```public BigInteger evaluateMod(BigInteger x,
BigInteger n)```
Evaluates this polynomial at the point x modulo n. The algorithm is naive and does not use the Horner scheme.
Parameters:
`x` - the argument value to be evaluated
`n` - the modulus
Returns:
the value of s(x) mod n, where s is this polynomial
• #### getDegree

`public BigInteger getDegree()`
Returns the degree of this polynomial. The degree is defined as the maximum exponent of the polynomial. Since this polynomial is sorted with respect to the exponents in descending order, the first key of this map is the degree. By definition, an empty polynomial has degree zero.
Returns:
the degree of this polynomial
• #### toBinaryString

`public String toBinaryString()`
Returns a binary string representation of this polynomial, where the j-the bit (counted from the right) is zero iff the coefficient of xj is zero. This repesentation is equivalent to this polynomial if the coefficients are all 0 or 1.
Returns:
a binary string representation of this polynomial
• #### toHTMLString

`public String toHTMLString()`
Returns a HTML string representation of this polynomial.
Returns:
a HTML string representation of this polynomial
• #### toString

`public String toString()`
Returns a string representation of this polynomial.
Overrides:
`toString` in class `AbstractMap<BigInteger,BigInteger>`
Returns:
a string representation of this polynomial