PolynomialZ

java.lang.Object
- java.util.AbstractMap<K,V>
- - java.util.TreeMap<BigInteger,BigInteger>
  - - org.mathIT.algebra.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) = a₀ + a₁ x + a₂ x² + ... + a_n xⁿ
where a₀, a₁, ..., a_n ∈ ℤ, and a_n ǂ 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,a_n>, ..., <0,a₀>]
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) = x¹⁰²³ - 3x² + 5x - 1
This class requires JDK 5 or higher.
Version:

1.1

Author:

Andreas de Vries

See Also:

Polynomial, Serialized Form

Nested Class Summary
- Nested classes/interfaces inherited from class java.util.AbstractMap
  AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>

Constructor Summary

Constructors
Constructor and Description
`PolynomialZ()` Creates an empty polynomial with a new `BigExponentComparator`.
`PolynomialZ(BigExponentComparator ec)` Creates an empty polynomial with the given `BigExponentComparator`.
`PolynomialZ(BigInteger exponent, BigInteger coefficient)` Creates a polynomial with a the single term a_e x^e and a new `BigExponentComparator`.
`PolynomialZ(BigInteger exponent, BigInteger coefficient, BigExponentComparator ec)` Creates a polynomial with a the single term a_e x^e and the given `BigExponentComparator`.

Method Summary

All Methods Instance Methods Concrete 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 s^e mod (x^r - 1, n) where s is this polynomial.
`PolynomialZ`	`modPow(int e, BigInteger n)` Returns the polynomial q^e mod (p, n) where q is this polynomial.
`PolynomialZ`	`modPow(PolynomialZ p, BigInteger e, BigInteger n)` Returns the polynomial q^e 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 a_e x^e 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 x^j 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()
```
    Creates an empty polynomial with a new BigExponentComparator.
  - 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 a_e x^e and a new BigExponentComparator.
    
    Parameters:
    
    exponent - the exponent e
    
    coefficient - the coefficient a_e
  - PolynomialZ
```
public PolynomialZ(BigInteger exponent,
                   BigInteger coefficient,
                   BigExponentComparator ec)
```
    Creates a polynomial with a the single term a_e x^e and the given BigExponentComparator.
    
    Parameters:
    
    exponent - the exponent e
    
    coefficient - the coefficient a_e
    
    ec - the comparator to compare exponents
- Method Detail
  - put
```
public BigInteger put(BigInteger exponent,
                      BigInteger coefficient)
```
    Adds the term a_e x^e to this polynomial. Here a_e 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 a_e x^e
    
    coefficient - the coefficient a_e in the term a_e x^e
    
    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
    
    See Also:
    
    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. 2^nd 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. 2^nd 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 q^e 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 q^e 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 s^e mod (x^r - 1, n) where s is this polynomial.
    
    Parameters:
    
    e - the exponent
    
    r - the degree of the monic polynomial x^r - 1
    
    n - the modulus
    
    Returns:
    
    s^e mod (x^r - 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 x^j 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

Class PolynomialZ

Nested Class Summary

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

Constructor Summary

Method Summary

Methods inherited from class java.util.TreeMap

Methods inherited from class java.util.AbstractMap

Methods inherited from class java.lang.Object

Methods inherited from interface java.util.Map

Constructor Detail

PolynomialZ

PolynomialZ

PolynomialZ

PolynomialZ

Method Detail

put

plus

plus

minus

minus

multiply

multiplyMod

multiplyMod2

divide

mod

mod

divideMod

modPow

modPow

modPow

evaluate

evaluateMod

getDegree

toBinaryString

toHTMLString

toString