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.

Integer

In [11]: galois.Poly.Int(268, field=GF)
Out[11]: Poly(x + 25, GF(3^5))

Binary string

In [12]: galois.Poly.Int(int("0b1011", 2))
Out[12]: Poly(x^3 + x + 1, GF(2))

Octal string

In [13]: galois.Poly.Int(int("0o5034", 8), field=galois.GF(2**3))
Out[13]: Poly(5x^3 + 3x + 4, GF(2^3))

Hex string

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(210x^4 + 5x^3 + 231x^2 + 32x + 166, 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.

Integer

In [30]: int(f)
Out[30]: 52

Binary string

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'

Octal string

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'

Hex string

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: May 17, 2022