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_1 x + a_0\) has coefficients \(\{a_{d}, a_{d-1}, \dots, a_1, a_0\}\) in \(\mathrm{GF}(p^m)\).

Parameters

coeffs (tuple, list, numpy.ndarray, galois.FieldArray) – The polynomial coefficients \(\{a_d, a_{d-1}, \dots, a_1, a_0\}\) with type galois.FieldArray. Alternatively, an iterable tuple, list, or numpy.ndarray may be provided and the Galois field domain is taken from the field keyword argument.
field (galois.FieldClass, optional) –
The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over.
- None (default): If the coefficients are a galois.FieldArray, they won’t be modified. If the coefficients are not explicitly in a Galois field, they are assumed to be from \(\mathrm{GF}(2)\) and are converted using galois.GF2(coeffs).
- galois.FieldClass: The coefficients are explicitly converted to this Galois field field(coeffs).
order (str, optional) –
The interpretation of the coefficient degrees.
- "desc" (default): The first element of coeffs is the highest degree coefficient, i.e. \(\{a_d, a_{d-1}, \dots, a_1, a_0\}\).
- "asc": The first element of coeffs is the lowest degree coefficient, i.e. \(\{a_0, a_1, \dots, a_{d-1}, a_d\}\).

Returns

The polynomial \(f(x)\).

Return type

galois.Poly

Examples

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

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

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

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

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

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

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

Polynomial arithmetic using binary operators.

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

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

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

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

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

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

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

# Compute both the quotient and remainder in one pass
In [13]: divmod(a, b)
Out[13]: (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 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 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 over \(\mathrm{GF}(p^m)\) from its roots.
`String`(string[, field])	Constructs a polynomial over \(\mathrm{GF}(p^m)\) from its string representation.
`Zero`([field])	Constructs the 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)\).
`reverse`()	Returns the \(d\)-th reversal \(x^d f(\frac{1}{x})\) of the polynomial \(f(x)\) with degree \(d\).
`roots`([multiplicity])	Calculates the roots \(r\) of the polynomial \(f(x)\), such that \(f(r) = 0\).

Special Methods

`__add__`(other)	Adds two polynomials.
`__divmod__`(other)	Divides two polynomials and returns the quotient and remainder.
`__floordiv__`(other)	Divides two polynomials and returns the quotient.
`__mod__`(other)	Divides two polynomials and returns the remainder.
`__mul__`(other)	Multiplies two polynomials.
`__pow__`(other)	Exponentiates the polynomial to an integer power.
`__sub__`(other)	Subtracts two polynomials.
`__truediv__`(other)	Divides two polynomials and returns the quotient.

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.
`string`	The string representation of the polynomial, without specifying the Galois field.

classmethod Degrees(degrees, coeffs=None, field=None)¶

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

Parameters

degrees (tuple, list, numpy.ndarray) – The polynomial degrees with non-zero coefficients.
coeffs (tuple, list, numpy.ndarray, galois.FieldArray, optional) – The corresponding non-zero polynomial coefficients with type galois.FieldArray. Alternatively, an iterable tuple, list, or numpy.ndarray may be provided and the Galois field domain is taken from the field keyword argument. The default is None which corresponds to all ones.
field (galois.FieldClass, optional) –
The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over.
- None (default): If the coefficients are a galois.FieldArray, they won’t be modified. If the coefficients are not explicitly in a Galois field, they are assumed to be from \(\mathrm{GF}(2)\) and are converted using galois.GF2(coeffs).
- galois.FieldClass: The coefficients are explicitly converted to this Galois field field(coeffs).

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 [1]: galois.Poly.Degrees([3,1,0])
Out[1]: Poly(x^3 + x + 1, GF(2))

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

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

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

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

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

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

Examples

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

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

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

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

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

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

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

Parameters

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

Returns

The polynomial \(f(x)\).

Return type

galois.Poly

Notes

The integer value \(i\) represents the polynomial \(f(x) = a_d x^{d} + a_{d-1} x^{d-1} + \dots + a_1 x + a_0\) over the 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.

Said differently, if the polynomial coefficients \(\{a_d, a_{d-1}, \dots, a_1, a_0\}\) are considered as the “digits” of a radix-\(p^m\) value, the polynomial’s integer representation is the decimal value (radix-\(10\)).

Examples

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

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

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

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

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

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

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

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

Examples

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

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

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

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

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

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

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

Parameters

degree (int) – The degree of the polynomial.
field (galois.FieldClass, optional) – The Galois 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 [1]: galois.Poly.Random(5)
Out[1]: Poly(x^5 + x^3 + x, GF(2))

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

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

In [3]: galois.Poly.Random(5, field=GF)
Out[3]: Poly(23x^5 + 215x^4 + 62x^3 + 150x^2 + 9x + 75, GF(2^8))

classmethod Roots(roots, multiplicities=None, field=None)¶

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

Parameters

roots (tuple, list, numpy.ndarray, galois.FieldArray) – The roots of the desired polynomial with type galois.FieldArray. Alternatively, an iterable tuple, list, or numpy.ndarray may be provided and the Galois field domain is taken from the field keyword argument.
multiplicities (tuple, list, numpy.ndarray, optional) – The corresponding root multiplicities. The default is None which corresponds to all ones, i.e. [1,]*len(roots).
field (galois.FieldClass, optional) –
The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over.
- None (default): If the roots are a galois.FieldArray, they won’t be modified. If the roots are not explicitly in a Galois field, they are assumed to be from \(\mathrm{GF}(2)\) and are converted using galois.GF2(roots).
- galois.FieldClass: The roots are explicitly converted to this Galois field field(roots).

Returns

The polynomial \(f(x)\).

Return type

galois.Poly

Notes

The polynomial \(f(x)\) with \(k\) roots \(\{r_1, r_2, \dots, r_k\}\) with multiplicities \(\{m_1, m_2, \dots, m_k\}\) is

\[ \begin{align}\begin{aligned}f(x) &= (x - r_1)^{m_1} (x - r_2)^{m_2} \dots (x - r_k)^{m_k}\\f(x) &= a_d x^d + a_{d-1} x^{d-1} + \dots + a_1 x + a_0\end{aligned}\end{align} \]

with degree \(d = \sum_{i=1}^{k} m_i\).

Examples

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

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

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

# Evaluate the polynomial at its roots
In [3]: p(roots)
Out[3]: GF([0, 0, 0], order=2)

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

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

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

In [6]: multiplicities = [1, 2, 1]

In [7]: p = galois.Poly.Roots(roots, multiplicities=multiplicities, field=GF); p
Out[7]: Poly(x^4 + 152x^3 + 85x^2 + 223x + 147, GF(2^8))

# Evaluate the polynomial at its roots
In [8]: p(roots)
Out[8]: GF([0, 0, 0], order=2^8)

classmethod String(string, field=<class 'numpy.ndarray over GF(2)'>)¶

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

Parameters

string (str) – The string representation of the polynomial \(f(x)\).
field (galois.FieldClass, optional) – The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is galois.GF2.

Returns

The polynomial \(f(x)\).

Return type

galois.Poly

Notes

The string parsing rules include:

Either ^ or ** may be used for indicating the polynomial degrees. For example, "13x^3 + 117" or "13x**3 + 117".
Multiplication operators * may be used between coefficients and the polynomial indeterminate x, but are not required. For example, "13x^3 + 117" or "13*x^3 + 117".
Polynomial coefficients of 1 may be specified or omitted. For example, "x^3 + 117" or "1*x^3 + 117".
The polynomial indeterminate can be any single character, but must be consistent. For example, "13x^3 + 117" or "13y^3 + 117".
Spaces are not required between terms. For example, "13x^3 + 117" or "13x^3+117".
Any combination of the above rules is acceptable.

Examples

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

In [1]: galois.Poly.String("x^2 + 1")
Out[1]: Poly(x^2 + 1, GF(2))

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

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

In [3]: galois.Poly.String("13x^3 + 117", field=GF)
Out[3]: Poly(13x^3 + 117, GF(2^8))

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

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

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

Examples

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

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

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

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

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

__add__(other)¶

Adds two polynomials.

Parameters: other (galois.Poly) – The polynomial \(b(x)\).
Returns: The polynomial \(c(x) = a(x) + b(x)\).
Return type: galois.Poly

Examples

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

In [2]: b = galois.Poly.Random(3); b
Out[2]: Poly(x^3, GF(2))

In [3]: a + b
Out[3]: Poly(x^5 + 1, GF(2))

__divmod__(other)¶

Divides two polynomials and returns the quotient and remainder.

Parameters

other (galois.Poly) – The polynomial \(b(x)\).

Returns

galois.Poly – The quotient polynomial \(q(x)\) such that \(a(x) = b(x)q(x) + r(x)\).
galois.Poly – The remainder polynomial \(r(x)\) such that \(a(x) = b(x)q(x) + r(x)\).

Examples

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

In [2]: b = galois.Poly.Random(3); b
Out[2]: Poly(x^3 + x^2 + x + 1, GF(2))

In [3]: q, r = divmod(a, b)

In [4]: q, r
Out[4]: (Poly(x^2 + x, GF(2)), Poly(1, GF(2)))

In [5]: b*q + r
Out[5]: Poly(x^5 + x + 1, GF(2))

__floordiv__(other)¶

Divides two polynomials and returns the quotient.

True division and floor division are equivalent.

Parameters: other (galois.Poly) – The polynomial \(b(x)\).
Returns: The quotient polynomial \(q(x)\) such that \(a(x) = b(x)q(x) + r(x)\).
Return type: galois.Poly

Examples

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

In [2]: b = galois.Poly.Random(3); b
Out[2]: Poly(x^3 + x^2 + 1, GF(2))

In [3]: divmod(a, b)
Out[3]: (Poly(x^2, GF(2)), Poly(x^2 + x + 1, GF(2)))

In [4]: a // b
Out[4]: Poly(x^2, GF(2))

__mod__(other)¶

Divides two polynomials and returns the remainder.

Parameters: other (galois.Poly) – The polynomial \(b(x)\).
Returns: The remainder polynomial \(r(x)\) such that \(a(x) = b(x)q(x) + r(x)\).
Return type: galois.Poly

Examples

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

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

In [3]: divmod(a, b)
Out[3]: (Poly(x^2, GF(2)), Poly(x^2 + x, GF(2)))

In [4]: a % b
Out[4]: Poly(x^2 + x, GF(2))

__mul__(other)¶

Multiplies two polynomials.

Parameters: other (galois.Poly) – The polynomial \(b(x)\).
Returns: The polynomial \(c(x) = a(x) b(x)\).
Return type: galois.Poly

Examples

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

In [2]: b = galois.Poly.Random(3); b
Out[2]: Poly(x^3 + x^2 + 1, GF(2))

In [3]: a * b
Out[3]: Poly(x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + x + 1, GF(2))

__pow__(other)¶

Exponentiates the polynomial to an integer power.

Parameters: other (int) – The non-negative integer exponent.
Returns: The polynomial \(a(x)**b\).
Return type: galois.Poly

Examples

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

In [2]: a**3
Out[2]: Poly(x^15 + x^14 + x^12 + x^10 + x^9, GF(2))

In [3]: a * a * a
Out[3]: Poly(x^15 + x^14 + x^12 + x^10 + x^9, GF(2))

__sub__(other)¶

Subtracts two polynomials.

Parameters: other (galois.Poly) – The polynomial \(b(x)\).
Returns: The polynomial \(c(x) = a(x) - b(x)\).
Return type: galois.Poly

Examples

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

In [2]: b = galois.Poly.Random(3); b
Out[2]: Poly(x^3 + x^2 + x + 1, GF(2))

In [3]: a - b
Out[3]: Poly(x^5 + x^2, GF(2))

__truediv__(other)¶

Divides two polynomials and returns the quotient.

True division and floor division are equivalent.

Parameters: other (galois.Poly) – The polynomial \(b(x)\).
Returns: The quotient polynomial \(q(x)\) such that \(a(x) = b(x)q(x) + r(x)\).
Return type: galois.Poly

Examples

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

In [2]: b = galois.Poly.Random(3); b
Out[2]: Poly(x^3, GF(2))

In [3]: divmod(a, b)
Out[3]: (Poly(x^2, GF(2)), Poly(x^2 + x + 1, GF(2)))

In [4]: a / b
Out[4]: Poly(x^2, GF(2))

derivative(k=1)¶

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

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

Notes

For the polynomial

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

the first formal derivative is defined as

\[f'(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. For example, \(3 \cdot a = a + a + a\).

References

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

Examples

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

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

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

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

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

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

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

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

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

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

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

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

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

In [11]: p = galois.Poly.Random(7, field=GF); p
Out[11]: Poly(142x^7 + 174x^6 + 225x^5 + 117x^4 + 178x^3 + 225x^2 + 197x + 14, GF(2^8))

In [12]: p.derivative()
Out[12]: Poly(142x^6 + 225x^4 + 178x^2 + 197, GF(2^8))

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

reverse()¶

Returns the \(d\)-th reversal \(x^d f(\frac{1}{x})\) of the polynomial \(f(x)\) with degree \(d\).

Returns: The \(n\)-th reversal \(x^n f(\frac{1}{x})\).
Return type: galois.Poly

Notes

For a polynomial \(f(x) = a_d x^d + a_{d-1} x^{d-1} + \dots + a_1 x + a_0\) with degree \(d\), the \(d\)-th reversal is equivalent to reversing the coefficients.

\[\textrm{rev}_d f(x) = x^d f(x^{-1}) = a_0 x^d + a_{1} x^{d-1} + \dots + a_{d-1} x + a_d\]

Examples

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

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

In [3]: f.reverse()
Out[3]: Poly(4x^3 + 3x^2 + 5, GF(7))

roots(multiplicity=False)¶

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

Parameters

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

Returns

galois.FieldArray – Galois field array of roots of \(f(x)\). The roots are ordered in increasing order.
np.ndarray – The multiplicity of each root, only returned if multiplicity=True.

Notes

This implementation uses Chien’s search to find the roots \(\{r_1, r_2, \dots, r_k\}\) 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_1)^{m_1} (x - r_2)^{m_2} \dots (x - r_k)^{m_k},\]

where \(m_i\) is the multiplicity of root \(r_i\) and \(d = \sum_{i=1}^{k} m_i\).

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 \(f(\alpha^i)\), where \(\alpha^i\) is a root of \(f(x)\) if \(f(\alpha^i) = 0\).

\[ \begin{align}\begin{aligned}f(\alpha^i) &= a_{d}(\alpha^i)^{d} + a_{d-1}(\alpha^i)^{d-1} + \dots + a_1(\alpha^i) + a_0\\f(\alpha^i) &\overset{\Delta}{=} \lambda_{i,d} + \lambda_{i,d-1} + \dots + \lambda_{i,1} + \lambda_{i,0}\\f(\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}f(\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\\f(\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\\f(\alpha^{i+1}) &= \lambda_{i,d}\alpha^d + \lambda_{i,d-1}\alpha^{d-1} + \dots + \lambda_{i,1}\alpha + \lambda_{i,0}\\f(\alpha^{i+1}) &= \sum_{j=0}^{d} \lambda_{i,j}\alpha^j\end{aligned}\end{align} \]

References

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

Examples

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

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

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

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

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

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

In [5]: p = galois.Poly.Roots([18,]*7 + [155,]*13 + [227,]*9, field=GF); p
Out[5]: 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 [6]: p.roots()
Out[6]: GF([ 18, 155, 227], order=2^8)

In [7]: p.roots(multiplicity=True)
Out[7]: (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 degrees are paired with coeffs.

Examples

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

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

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

Type: galois.FieldArray

property degree¶

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

Examples

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

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

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

Type: int

property degrees¶

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

Examples

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

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

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

Type: numpy.ndarray

property field¶

The Galois field array class to which the coefficients belong.

Examples

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

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

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

In [4]: b = galois.Poly.Random(5, field=GF); b
Out[4]: Poly(9x^5 + 138x^4 + 91x^3 + 41x^2 + 196x + 109, GF(2^8))

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

Type: galois.FieldClass

property integer¶

The integer representation of the polynomial. For the polynomial \(f(x) = a_d x^d + a_{d-1} x^{d-1} + \dots + a_1 x + a_0\) over the field \(\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.

Said differently, if the polynomial coefficients \(\{a_d, a_{d-1}, \dots, a_1, a_0\}\) are considered as the “digits” of a radix-\(p^m\) value, the polynomial’s integer representation is the decimal value (radix-\(10\)).

Examples

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

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

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

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

Type: int

property nonzero_coeffs¶

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

Examples

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

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

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

Type: galois.FieldArray

property nonzero_degrees¶

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

Examples

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

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

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

Type: numpy.ndarray

property string¶

The string representation of the polynomial, without specifying the Galois field.

Examples

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

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

In [3]: p.string
Out[3]: '3x^3 + 5x + 2'

Type: str