# Polynomials¶

Univariate polynomials over finite fields are supported with the `Poly` class.

## Create a polynomial¶

Create a polynomial by specifying its coefficients in degree-descending order and the finite field its over.

``````In [1]: GF = galois.GF(2**8)

In [2]: galois.Poly([1, 0, 0, 55, 23], field=GF)
Out[2]: Poly(x^4 + 55x + 23, GF(2^8))
``````

Or pass a `FieldArray` of coefficients without explicitly specifying the finite field.

``````In [3]: coeffs = GF([1, 0, 0, 55, 23]); coeffs
Out[3]: GF([ 1,  0,  0, 55, 23], order=2^8)

In [4]: galois.Poly(coeffs)
Out[4]: Poly(x^4 + 55x + 23, GF(2^8))
``````

Tip

Use `set_printoptions()` to display the polynomial coefficients in degree-ascending order.

## Element representation¶

As with `FieldArray` instances, the finite field element representation of the polynomial coefficients may be changed by setting the `display` keyword argument of `GF()` or using the `display()` classmethod.

``````In [5]: GF = galois.GF(3**5)

# Display f(x) using the default integer representation
In [6]: f = galois.Poly([13, 0, 4, 2], field=GF); print(f)
13x^3 + 4x + 2

# Display f(x) using the polynomial representation
In [7]: GF.display("poly"); print(f)
(α^2 + α + 1)x^3 + (α + 1)x + 2

# Display f(x) using the power representation
In [8]: GF.display("power"); print(f)
(α^10)x^3 + (α^69)x + α^121

In [9]: GF.display("int");
``````

See Element Representation for more details.

## Alternate constructors¶

There are several additional ways to create a polynomial. These alternate constructors are included as classmethods in `Poly`. By convention, alternate constructors use `PascalCase` while other classmethods use `snake_case`.

Create a polynomial by specifying its non-zero degrees and coefficients using `Degrees()`.

``````In [10]: galois.Poly.Degrees([1000, 1], coeffs=[1, 179], field=GF)
Out[10]: Poly(x^1000 + 179x, GF(3^5))
``````

Create a polynomial from its integer representation using `Int()`. Additionally, one may create a polynomial from a binary, octal, or hexadecimal string of its integer representation.

``````In [11]: galois.Poly.Int(268, field=GF)
Out[11]: Poly(x + 25, GF(3^5))
``````
``````In [12]: galois.Poly.Int(int("0b1011", 2))
Out[12]: Poly(x^3 + x + 1, GF(2))
``````
``````In [13]: galois.Poly.Int(int("0o5034", 8), field=galois.GF(2**3))
Out[13]: Poly(5x^3 + 3x + 4, GF(2^3))
``````
``````In [14]: galois.Poly.Int(int("0xf700a275", 16), field=galois.GF(2**8))
Out[14]: Poly(247x^3 + 162x + 117, GF(2^8))
``````

Create a polynomial from its string representation using `Str()`.

``````In [15]: galois.Poly.Str("x^5 + 143", field=GF)
Out[15]: Poly(x^5 + 143, GF(3^5))
``````

Create a polynomial from its roots using `Roots()`.

``````In [16]: f = galois.Poly.Roots([137, 22, 51], field=GF); f
Out[16]: Poly(x^3 + 180x^2 + 19x + 58, GF(3^5))

In [17]: f.roots()
Out[17]: GF([ 22,  51, 137], order=3^5)
``````

The `Zero()`, `One()`, and `Identity()` classmethods create common, simple polynomials. They are included for convenience.

``````In [18]: galois.Poly.Zero(GF)
Out[18]: Poly(0, GF(3^5))

In [19]: galois.Poly.One(GF)
Out[19]: Poly(1, GF(3^5))

In [20]: galois.Poly.Identity(GF)
Out[20]: Poly(x, GF(3^5))
``````

Random polynomials of a given degree are easily created with `Random()`.

``````In [21]: galois.Poly.Random(4, field=GF)
Out[21]: Poly(171x^4 + 87x^3 + 43x^2 + 239x + 71, GF(3^5))
``````

## Methods¶

Polynomial objects have several methods that modify or perform operations on the polynomial. Below are some examples.

Compute the derivative of a polynomial using `derivative()`.

``````In [22]: GF = galois.GF(7)

In [23]: f = galois.Poly([1, 0, 5, 2, 3], field=GF); f
Out[23]: Poly(x^4 + 5x^2 + 2x + 3, GF(7))

In [24]: f.derivative()
Out[24]: Poly(4x^3 + 3x + 2, GF(7))
``````

Compute the roots of a polynomial using `roots()`.

``````In [25]: f.roots()
Out[25]: GF([5, 6], order=7)
``````

## Properties¶

Polynomial objects have several instance properties. Below are some examples.

Find the non-zero degrees and coefficients of the polynomial using `nonzero_degrees` and `nonzero_coeffs`.

``````In [26]: GF = galois.GF(7)

In [27]: f = galois.Poly([1, 0, 3], field=GF); f
Out[27]: Poly(x^2 + 3, GF(7))

In [28]: f.nonzero_degrees
Out[28]: array([2, 0])

In [29]: f.nonzero_coeffs
Out[29]: GF([1, 3], order=7)
``````

Find the integer equivalent of the polynomial using `int()`, see `__int__()`. Additionally, one may convert a polynomial into the binary, octal, or hexadecimal string of its integer representation.

``````In [30]: int(f)
Out[30]: 52
``````
``````In [31]: g = galois.Poly([1, 0, 1, 1]); g
Out[31]: Poly(x^3 + x + 1, GF(2))

In [32]: bin(g)
Out[32]: '0b1011'
``````
``````In [33]: g = galois.Poly([5, 0, 3, 4], field=galois.GF(2**3)); g
Out[33]: Poly(5x^3 + 3x + 4, GF(2^3))

In [34]: oct(g)
Out[34]: '0o5034'
``````
``````In [35]: g = galois.Poly([0xf7, 0x00, 0xa2, 0x75], field=galois.GF(2**8)); g
Out[35]: Poly(247x^3 + 162x + 117, GF(2^8))

In [36]: hex(g)
Out[36]: '0xf700a275'
``````

Get the string representation of the polynomial using `str()`.

``````In [37]: str(f)
Out[37]: 'x^2 + 3'
``````

## Special polynomials¶

The `galois` library also includes several functions to find certain special polynomials. Below are some examples.

Find one or all irreducible polynomials with `irreducible_poly()` and `irreducible_polys()`.

``````In [38]: galois.irreducible_poly(3, 3)
Out[38]: Poly(x^3 + 2x + 1, GF(3))

In [39]: list(galois.irreducible_polys(3, 3))
Out[39]:
[Poly(x^3 + 2x + 1, GF(3)),
Poly(x^3 + 2x + 2, GF(3)),
Poly(x^3 + x^2 + 2, GF(3)),
Poly(x^3 + x^2 + x + 2, GF(3)),
Poly(x^3 + x^2 + 2x + 1, GF(3)),
Poly(x^3 + 2x^2 + 1, GF(3)),
Poly(x^3 + 2x^2 + x + 1, GF(3)),
Poly(x^3 + 2x^2 + 2x + 2, GF(3))]
``````

Find one or all primitive polynomials with `primitive_poly()` and `primitive_polys()`.

``````In [40]: galois.primitive_poly(3, 3)
Out[40]: Poly(x^3 + 2x + 1, GF(3))

In [41]: list(galois.primitive_polys(3, 3))
Out[41]:
[Poly(x^3 + 2x + 1, GF(3)),
Poly(x^3 + x^2 + 2x + 1, GF(3)),
Poly(x^3 + 2x^2 + 1, GF(3)),
Poly(x^3 + 2x^2 + x + 1, GF(3))]
``````

Find the Conway polynomial using `conway_poly()`.

``````In [42]: galois.conway_poly(3, 3)
Out[42]: Poly(x^3 + 2x + 1, GF(3))
``````

Last update: Jul 12, 2022