galois.Poly¶

class galois.Poly(coeffs, field=None, order='desc')¶

Create a polynomial \(f(x)\) over \(\mathrm{GF}(p^m)\).

The polynomial \(f(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\) has coefficients \(\{a_{d}, a_{d-1}, \dots, a_1, a_0\}\) in \(\mathrm{GF}(p^m)\).

Parameters

coeffs (array_like) – List of polynomial coefficients \(\{a_{d}, a_{d-1}, \dots, a_1, a_0\}\) with type galois.GFArray, numpy.ndarray, list, or tuple. The first element is the highest-degree element if order="desc" or the first element is the 0-th degree element if order="asc".
field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is None which represents galois.GF2. If coeffs is a Galois field array, then that field is used and the field argument is ignored.
order (str, optional) – The interpretation of the coefficient degrees, either "desc" (default) or "asc". For "desc", the first element of coeffs is the highest degree coefficient \(x^{d}\)) and the last element is the 0-th degree element \(x^0\).

Returns

The polynomial \(f(x)\).

Return type

galois.Poly

Examples

Create a polynomial over \(\mathrm{GF}(2)\).

In [245]: galois.Poly([1,0,1,1])
Out[245]: Poly(x^3 + x + 1, GF(2))

In [246]: galois.Poly.Degrees([3,1,0])
Out[246]: Poly(x^3 + x + 1, GF(2))

Create a polynomial over \(\mathrm{GF}(2^8)\).

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

In [248]: galois.Poly([124,0,223,0,0,15], field=GF)
Out[248]: Poly(124x^5 + 223x^3 + 15, GF(2^8))

# Alternate way of constructing the same polynomial
In [249]: galois.Poly.Degrees([5,3,0], coeffs=[124,223,15], field=GF)
Out[249]: Poly(124x^5 + 223x^3 + 15, GF(2^8))

Polynomial arithmetic using binary operators.

In [250]: a = galois.Poly([117,0,63,37], field=GF); a
Out[250]: Poly(117x^3 + 63x + 37, GF(2^8))

In [251]: b = galois.Poly([224,0,21], field=GF); b
Out[251]: Poly(224x^2 + 21, GF(2^8))

In [252]: a + b
Out[252]: Poly(117x^3 + 224x^2 + 63x + 48, GF(2^8))

In [253]: a - b
Out[253]: Poly(117x^3 + 224x^2 + 63x + 48, GF(2^8))

# Compute the quotient of the polynomial division
In [254]: a / b
Out[254]: Poly(202x, GF(2^8))

# True division and floor division are equivalent
In [255]: a / b == a // b
Out[255]: True

# Compute the remainder of the polynomial division
In [256]: a % b
Out[256]: Poly(198x + 37, GF(2^8))

# Compute both the quotient and remainder in one pass
In [257]: divmod(a, b)
Out[257]: (Poly(202x, GF(2^8)), Poly(198x + 37, GF(2^8)))

Constructors

`Degrees`(degrees[, coeffs, field])	Constructs a polynomial over \(\mathrm{GF}(p^m)\) from its non-zero degrees.
`Identity`([field])	Constructs the identity polynomial \(f(x) = x\) over \(\mathrm{GF}(p^m)\).
`Integer`(integer[, field])	Constructs a polynomial over \(\mathrm{GF}(p^m)\) from its integer representation.
`One`([field])	Constructs the one polynomial \(f(x) = 1\) over \(\mathrm{GF}(p^m)\).
`Random`(degree[, field])	Constructs a random polynomial over \(\mathrm{GF}(p^m)\) with degree \(d\).
`Roots`(roots[, multiplicities, field])	Constructs a monic polynomial in \(\mathrm{GF}(p^m)[x]\) from its roots.
`Zero`([field])	Constructs the zero polynomial \(f(x) = 0\) over \(\mathrm{GF}(p^m)\).

Methods

`derivative`([k])	Computes the \(k\)-th formal derivative \(\frac{d^k}{dx^k} f(x)\) of the polynomial \(f(x)\).
`roots`([multiplicity])	Calculates the roots \(r\) of the polynomial \(f(x)\), such that \(f(r) = 0\).

Attributes

`coeffs`	The coefficients of the polynomial in degree-descending order.
`degree`	The degree of the polynomial, i.e. the highest degree with non-zero coefficient.
`degrees`	An array of the polynomial degrees in degree-descending order.
`field`	The Galois field array class to which the coefficients belong.
`integer`	The integer representation of the polynomial.
`nonzero_coeffs`	The non-zero coefficients of the polynomial in degree-descending order.
`nonzero_degrees`	An array of the polynomial degrees that have non-zero coefficients, in degree-descending order.

classmethod Degrees(degrees, coeffs=None, field=None)[source]¶

Constructs a polynomial over \(\mathrm{GF}(p^m)\) from its non-zero degrees.

Parameters

degrees (list) – List of polynomial degrees with non-zero coefficients.
coeffs (array_like, optional) – List of corresponding non-zero coefficients. The default is None which corresponds to all one coefficients, i.e. [1,]*len(degrees).
field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is`None` which represents galois.GF2.

Returns

The polynomial \(f(x)\).

Return type

galois.Poly

Examples

Construct a polynomial over \(\mathrm{GF}(2)\) by specifying the degrees with non-zero coefficients.

In [258]: galois.Poly.Degrees([3,1,0])
Out[258]: Poly(x^3 + x + 1, GF(2))

Construct a polynomial over \(\mathrm{GF}(2^8)\) by specifying the degrees with non-zero coefficients.

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

In [260]: galois.Poly.Degrees([3,1,0], coeffs=[251,73,185], field=GF)
Out[260]: Poly(251x^3 + 73x + 185, GF(2^8))

classmethod Identity(field=<class 'numpy.ndarray over GF(2)'>)[source]¶

Constructs the identity polynomial \(f(x) = x\) over \(\mathrm{GF}(p^m)\).

Parameters: field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is galois.GF2.
Returns: The polynomial \(f(x)\).
Return type: galois.Poly

Examples

Construct the identity polynomial over \(\mathrm{GF}(2)\).

In [261]: galois.Poly.Identity()
Out[261]: Poly(x, GF(2))

Construct the identity polynomial over \(\mathrm{GF}(2^8)\).

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

In [263]: galois.Poly.Identity(field=GF)
Out[263]: Poly(x, GF(2^8))

classmethod Integer(integer, field=<class 'numpy.ndarray over GF(2)'>)[source]¶

Constructs a polynomial over \(\mathrm{GF}(p^m)\) from its integer representation.

The integer value \(i\) represents the polynomial \(f(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\) over field \(\mathrm{GF}(p^m)\) if \(i = a_{d}(p^m)^{d} + a_{d-1}(p^m)^{d-1} + \dots + a_1(p^m) + a_0\) using integer arithmetic, not finite field arithmetic.

Parameters

integer (int) – The integer representation of the polynomial \(f(x)\).
field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is galois.GF2.

Returns

The polynomial \(f(x)\).

Return type

galois.Poly

Examples

Construct a polynomial over \(\mathrm{GF}(2)\) from its integer representation.

In [264]: galois.Poly.Integer(5)
Out[264]: Poly(x^2 + 1, GF(2))

Construct a polynomial over \(\mathrm{GF}(2^8)\) from its integer representation.

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

In [266]: galois.Poly.Integer(13*256**3 + 117, field=GF)
Out[266]: Poly(13x^3 + 117, GF(2^8))

classmethod One(field=<class 'numpy.ndarray over GF(2)'>)[source]¶

Constructs the one polynomial \(f(x) = 1\) over \(\mathrm{GF}(p^m)\).

Parameters: field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is galois.GF2.
Returns: The polynomial \(f(x)\).
Return type: galois.Poly

Examples

Construct the one polynomial over \(\mathrm{GF}(2)\).

In [267]: galois.Poly.One()
Out[267]: Poly(1, GF(2))

Construct the one polynomial over \(\mathrm{GF}(2^8)\).

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

In [269]: galois.Poly.One(field=GF)
Out[269]: Poly(1, GF(2^8))

classmethod Random(degree, field=<class 'numpy.ndarray over GF(2)'>)[source]¶

Constructs a random polynomial over \(\mathrm{GF}(p^m)\) with degree \(d\).

Parameters

degree (int) – The degree of the polynomial.
field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is galois.GF2.

Returns

The polynomial \(f(x)\).

Return type

galois.Poly

Examples

Construct a random degree-\(5\) polynomial over \(\mathrm{GF}(2)\).

In [270]: galois.Poly.Random(5)
Out[270]: Poly(x^5 + x^3 + x^2 + 1, GF(2))

Construct a random degree-\(5\) polynomial over \(\mathrm{GF}(2^8)\).

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

In [272]: galois.Poly.Random(5, field=GF)
Out[272]: Poly(5x^5 + 19x^4 + 151x^3 + 180x^2 + 117x + 14, GF(2^8))

classmethod Roots(roots, multiplicities=None, field=None)[source]¶

Constructs a monic polynomial in \(\mathrm{GF}(p^m)[x]\) from its roots.

The polynomial \(f(x)\) with \(d\) roots \(\{r_0, r_1, \dots, r_{d-1}\}\) is:

\[ \begin{align}\begin{aligned}f(x) &= (x - r_0) (x - r_1) \dots (x - r_{d-1})\\f(x) &= a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\end{aligned}\end{align} \]

Parameters

roots (array_like) – List of roots in \(\mathrm{GF}(p^m)\) of the desired polynomial.
multiplicities (array_like, optional) – List of multiplicity of each root. The default is None which corresponds to all ones.
field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is`None` which represents galois.GF2.

Returns

The polynomial \(f(x)\).

Return type

galois.Poly

Examples

Construct a polynomial over \(\mathrm{GF}(2)\) from a list of its roots.

In [273]: roots = [0, 0, 1]

In [274]: p = galois.Poly.Roots(roots); p
Out[274]: Poly(x^3 + x^2, GF(2))

In [275]: p(roots)
Out[275]: GF([0, 0, 0], order=2)

Construct a polynomial over \(\mathrm{GF}(2^8)\) from a list of its roots.

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

In [277]: roots = [121, 198, 225]

In [278]: p = galois.Poly.Roots(roots, field=GF); p
Out[278]: Poly(x^3 + 94x^2 + 174x + 89, GF(2^8))

In [279]: p(roots)
Out[279]: GF([0, 0, 0], order=2^8)

classmethod Zero(field=<class 'numpy.ndarray over GF(2)'>)[source]¶

Constructs the zero polynomial \(f(x) = 0\) over \(\mathrm{GF}(p^m)\).

Parameters: field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is galois.GF2.
Returns: The polynomial \(f(x)\).
Return type: galois.Poly

Examples

Construct the zero polynomial over \(\mathrm{GF}(2)\).

In [280]: galois.Poly.Zero()
Out[280]: Poly(0, GF(2))

Construct the zero polynomial over \(\mathrm{GF}(2^8)\).

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

In [282]: galois.Poly.Zero(field=GF)
Out[282]: Poly(0, GF(2^8))

derivative(k=1)[source]¶

Computes the \(k\)-th formal derivative \(\frac{d^k}{dx^k} f(x)\) of the polynomial \(f(x)\).

For the polynomial

\[f(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\]

the first formal derivative is defined as

\[p'(x) = (d) \cdot a_{d} x^{d-1} + (d-1) \cdot a_{d-1} x^{d-2} + \dots + (2) \cdot a_{2} x + a_1\]

where \(\cdot\) represents scalar multiplication (repeated addition), not finite field multiplication, e.g. \(3 \cdot a = a + a + a\).

Parameters: k (int, optional) – The number of derivatives to compute. 1 corresponds to \(p'(x)\), 2 corresponds to \(p''(x)\), etc. The default is 1.
Returns: The \(k\)-th formal derivative of the polynomial \(f(x)\).
Return type: galois.Poly

References

https://en.wikipedia.org/wiki/Formal_derivative

Examples

Compute the derivatives of a polynomial over \(\mathrm{GF}(2)\).

In [283]: p = galois.Poly.Random(7); p
Out[283]: Poly(x^7 + x^4 + x^3 + x, GF(2))

In [284]: p.derivative()
Out[284]: Poly(x^6 + x^2 + 1, GF(2))

# k derivatives of a polynomial where k is the Galois field's characteristic will always result in 0
In [285]: p.derivative(2)
Out[285]: Poly(0, GF(2))

Compute the derivatives of a polynomial over \(\mathrm{GF}(7)\).

In [286]: GF = galois.GF(7)

In [287]: p = galois.Poly.Random(11, field=GF); p
Out[287]: Poly(5x^11 + 6x^10 + 5x^9 + 4x^8 + 6x^7 + x^6 + x^5 + x^4 + 4x^3 + 2x^2 + 2x + 6, GF(7))

In [288]: p.derivative()
Out[288]: Poly(6x^10 + 4x^9 + 3x^8 + 4x^7 + 6x^5 + 5x^4 + 4x^3 + 5x^2 + 4x + 2, GF(7))

In [289]: p.derivative(2)
Out[289]: Poly(4x^9 + x^8 + 3x^7 + 2x^4 + 6x^3 + 5x^2 + 3x + 4, GF(7))

In [290]: p.derivative(3)
Out[290]: Poly(x^8 + x^7 + x^3 + 4x^2 + 3x + 3, GF(7))

# k derivatives of a polynomial where k is the Galois field's characteristic will always result in 0
In [291]: p.derivative(7)
Out[291]: Poly(0, GF(2))

Compute the derivatives of a polynomial over \(\mathrm{GF}(2^8)\).

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

In [293]: p = galois.Poly.Random(7, field=GF); p
Out[293]: Poly(73x^7 + 54x^6 + 241x^5 + 101x^4 + 131x^3 + 5x^2 + 188x + 98, GF(2^8))

In [294]: p.derivative()
Out[294]: Poly(73x^6 + 241x^4 + 131x^2 + 188, GF(2^8))

# k derivatives of a polynomial where k is the Galois field's characteristic will always result in 0
In [295]: p.derivative(2)
Out[295]: Poly(0, GF(2^8))

roots(multiplicity=False)[source]¶

Calculates the roots \(r\) of the polynomial \(f(x)\), such that \(f(r) = 0\).

This implementation uses Chien’s search to find the roots \(\{r_0, r_1, \dots, r_{k-1}\}\) of the degree-\(d\) polynomial

\[f(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0,\]

where \(k \le d\). Then, \(f(x)\) can be factored as

\[f(x) = (x - r_0)^{m_0} (x - r_1)^{m_1} \dots (x - r_{k-1})^{m_{k-1}},\]

where \(m_i\) is the multiplicity of root \(r_i\) and

\[\sum_{i=0}^{k-1} m_i = d.\]

The Galois field elements can be represented as \(\mathrm{GF}(p^m) = \{0, 1, \alpha, \alpha^2, \dots, \alpha^{p^m-2}\}\), where \(\alpha\) is a primitive element of \(\mathrm{GF}(p^m)\).

\(0\) is a root of \(f(x)\) if:

\[a_0 = 0\]

\(1\) is a root of \(f(x)\) if:

\[\sum_{j=0}^{d} a_j = 0\]

The remaining elements of \(\mathrm{GF}(p^m)\) are powers of \(\alpha\). The following equations calculate \(p(\alpha^i)\), where \(\alpha^i\) is a root of \(f(x)\) if \(p(\alpha^i) = 0\).

\[ \begin{align}\begin{aligned}p(\alpha^i) &= a_{d}(\alpha^i)^{d} + a_{d-1}(\alpha^i)^{d-1} + \dots + a_1(\alpha^i) + a_0\\p(\alpha^i) &\overset{\Delta}{=} \lambda_{i,d} + \lambda_{i,d-1} + \dots + \lambda_{i,1} + \lambda_{i,0}\\p(\alpha^i) &= \sum_{j=0}^{d} \lambda_{i,j}\end{aligned}\end{align} \]

The next power of \(\alpha\) can be easily calculated from the previous calculation.

\[ \begin{align}\begin{aligned}p(\alpha^{i+1}) &= a_{d}(\alpha^{i+1})^{d} + a_{d-1}(\alpha^{i+1})^{d-1} + \dots + a_1(\alpha^{i+1}) + a_0\\p(\alpha^{i+1}) &= a_{d}(\alpha^i)^{d}\alpha^d + a_{d-1}(\alpha^i)^{d-1}\alpha^{d-1} + \dots + a_1(\alpha^i)\alpha + a_0\\p(\alpha^{i+1}) &= \lambda_{i,d}\alpha^d + \lambda_{i,d-1}\alpha^{d-1} + \dots + \lambda_{i,1}\alpha + \lambda_{i,0}\\p(\alpha^{i+1}) &= \sum_{j=0}^{d} \lambda_{i,j}\alpha^j\end{aligned}\end{align} \]

Parameters

multiplicity (bool, optional) – Optionally return the multiplicity of each root. The default is False, which only returns the unique roots.

Returns

galois.GFArray – Galois field array of roots of \(f(x)\).
np.ndarray – The multiplicity of each root. Only returned if multiplicity=True.

References

https://en.wikipedia.org/wiki/Chien_search

Examples

Find the roots of a polynomial over \(\mathrm{GF}(2)\).

In [296]: p = galois.Poly.Roots([0,]*7 + [1,]*13); p
Out[296]: Poly(x^20 + x^19 + x^16 + x^15 + x^12 + x^11 + x^8 + x^7, GF(2))

In [297]: p.roots()
Out[297]: GF([0, 1], order=2)

In [298]: p.roots(multiplicity=True)
Out[298]: (GF([0, 1], order=2), array([ 7, 13]))

Find the roots of a polynomial over \(\mathrm{GF}(2^8)\).

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

In [300]: p = galois.Poly.Roots([18,]*7 + [155,]*13 + [227,]*9, field=GF); p
Out[300]: Poly(x^29 + 106x^28 + 27x^27 + 155x^26 + 230x^25 + 38x^24 + 78x^23 + 8x^22 + 46x^21 + 210x^20 + 248x^19 + 214x^18 + 172x^17 + 152x^16 + 82x^15 + 237x^14 + 172x^13 + 230x^12 + 141x^11 + 63x^10 + 103x^9 + 167x^8 + 199x^7 + 127x^6 + 254x^5 + 95x^4 + 93x^3 + 3x^2 + 4x + 208, GF(2^8))

In [301]: p.roots()
Out[301]: GF([ 18, 155, 227], order=2^8)

In [302]: p.roots(multiplicity=True)
Out[302]: (GF([ 18, 155, 227], order=2^8), array([ 7, 13,  9]))

property coeffs¶

The coefficients of the polynomial in degree-descending order. The entries of galois.Poly.degrees are paired with galois.Poly.coeffs.

Examples

In [303]: GF = galois.GF(7)

In [304]: p = galois.Poly([3, 0, 5, 2], field=GF)

In [305]: p.coeffs
Out[305]: GF([3, 0, 5, 2], order=7)

Type: galois.GFArray

property degree¶

The degree of the polynomial, i.e. the highest degree with non-zero coefficient.

Examples

In [306]: GF = galois.GF(7)

In [307]: p = galois.Poly([3, 0, 5, 2], field=GF)

In [308]: p.degree
Out[308]: 3

Type: int

property degrees¶

An array of the polynomial degrees in degree-descending order. The entries of galois.Poly.degrees are paired with galois.Poly.coeffs.

Examples

In [309]: GF = galois.GF(7)

In [310]: p = galois.Poly([3, 0, 5, 2], field=GF)

In [311]: p.degrees
Out[311]: array([3, 2, 1, 0])

Type: numpy.ndarray

property field¶

The Galois field array class to which the coefficients belong.

Examples

In [312]: a = galois.Poly.Random(5); a
Out[312]: Poly(x^5, GF(2))

In [313]: a.field
Out[313]: <class 'numpy.ndarray over GF(2)'>

In [314]: b = galois.Poly.Random(5, field=galois.GF(2**8)); b
Out[314]: Poly(46x^5 + 56x^4 + 20x^3 + 9x^2 + 203x + 142, GF(2^8))

In [315]: b.field
Out[315]: <class 'numpy.ndarray over GF(2^8)'>

Type: galois.GFMeta

property integer¶

The integer representation of the polynomial. For polynomial \(f(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\) with elements in \(a_k \in \mathrm{GF}(p^m)\), the integer representation is \(i = a_{d} (p^m)^{d} + a_{d-1} (p^m)^{d-1} + \dots + a_1 (p^m) + a_0\) (using integer arithmetic, not finite field arithmetic).

Examples

In [316]: GF = galois.GF(7)

In [317]: p = galois.Poly([3, 0, 5, 2], field=GF)

In [318]: p.integer
Out[318]: 1066

In [319]: p.integer == 3*7**3 + 5*7**1 + 2*7**0
Out[319]: True

Type: int

property nonzero_coeffs¶

The non-zero coefficients of the polynomial in degree-descending order. The entries of galois.Poly.nonzero_degrees are paired with galois.Poly.nonzero_coeffs.

Examples

In [320]: GF = galois.GF(7)

In [321]: p = galois.Poly([3, 0, 5, 2], field=GF)

In [322]: p.nonzero_coeffs
Out[322]: GF([3, 5, 2], order=7)

Type: galois.GFArray

property nonzero_degrees¶

An array of the polynomial degrees that have non-zero coefficients, in degree-descending order. The entries of galois.Poly.nonzero_degrees are paired with galois.Poly.nonzero_coeffs.

Examples

In [323]: GF = galois.GF(7)

In [324]: p = galois.Poly([3, 0, 5, 2], field=GF)

In [325]: p.nonzero_degrees
Out[325]: array([3, 1, 0])

Type: numpy.ndarray