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

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


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

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

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

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


Polynomial arithmetic using binary operators.

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

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

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

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

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

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

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

# Compute both the quotient and remainder in one pass
In : divmod(a, b)
Out: (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)$$. 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
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 : galois.Poly.Degrees([3,1,0])
Out: Poly(x^3 + x + 1, GF(2))


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

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

In : galois.Poly.Degrees([3,1,0], coeffs=[251,73,185], field=GF)
Out: 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 : galois.Poly.Identity()
Out: Poly(x, GF(2))


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

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

In : galois.Poly.Identity(field=GF)
Out: 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
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 : galois.Poly.Integer(5)
Out: Poly(x^2 + 1, GF(2))


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

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

In : galois.Poly.Integer(13*256**3 + 117, field=GF)
Out: 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 : galois.Poly.One()
Out: Poly(1, GF(2))


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

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

In : galois.Poly.One(field=GF)
Out: 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
Returns

The polynomial $$f(x)$$.

Return type

galois.Poly

Examples

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

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


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

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

In : galois.Poly.Random(5, field=GF)
Out: 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
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 : roots = [0, 0, 1]

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

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


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

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

In : roots = [121, 198, 225]

In : multiplicities = [1, 2, 1]

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

# Evaluate the polynomial at its roots
In : p(roots)
Out: 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
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 : galois.Poly.String("x^2 + 1")
Out: Poly(x^2 + 1, GF(2))


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

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

In : galois.Poly.String("13x^3 + 117", field=GF)
Out: 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 : galois.Poly.Zero()
Out: Poly(0, GF(2))


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

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

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


Parameters

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

Returns

The polynomial $$c(x) = a(x) + b(x)$$.

Return type

galois.Poly

Examples

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

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

In : a + b
Out: 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 : a = galois.Poly.Random(5); a
Out: Poly(x^5 + x + 1, GF(2))

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

In : q, r = divmod(a, b)

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

In : b*q + r
Out: 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 : a = galois.Poly.Random(5); a
Out: Poly(x^5 + x^4 + x + 1, GF(2))

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

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

In : a // b
Out: 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 : a = galois.Poly.Random(5); a
Out: Poly(x^5 + x^4 + x^2 + x, GF(2))

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

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

In : a % b
Out: 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 : a = galois.Poly.Random(5); a
Out: Poly(x^5 + x^3 + x + 1, GF(2))

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

In : a * b
Out: 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 : a = galois.Poly.Random(5); a
Out: Poly(x^5 + x^4 + x^3, GF(2))

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

In : a * a * a
Out: 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 : a = galois.Poly.Random(5); a
Out: Poly(x^5 + x^3 + x + 1, GF(2))

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

In : a - b
Out: 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 : a = galois.Poly.Random(5); a
Out: Poly(x^5 + x^2 + x + 1, GF(2))

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

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

In : a / b
Out: 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

Examples

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

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

In : p.derivative()
Out: 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 : p.derivative(2)
Out: Poly(0, GF(2))


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

In : GF = galois.GF(7)

In : p = galois.Poly.Random(11, field=GF); p
Out: 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 : p.derivative()
Out: Poly(4x^10 + 3x^9 + x^8 + 6x^7 + 3x^5 + 3x^4 + 5x^3 + x^2 + 5x + 3, GF(7))

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

In : p.derivative(3)
Out: 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 : p.derivative(7)
Out: Poly(0, GF(7))


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

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

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

In : p.derivative()
Out: 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 : p.derivative(2)
Out: 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 : GF = galois.GF(7)

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

In : f.reverse()
Out: 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

Examples

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

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

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

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


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

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

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

In : p.roots(multiplicity=True)
Out: (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 : GF = galois.GF(7)

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

In : p.coeffs
Out: 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 : GF = galois.GF(7)

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

In : p.degree
Out: 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 : GF = galois.GF(7)

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

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

Type

numpy.ndarray

property field

The Galois field array class to which the coefficients belong.

Examples

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

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

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

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

In : b.field
Out: <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 : GF = galois.GF(7)

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

In : p.integer
Out: 1066

In : p.integer == 3*7**3 + 5*7**1 + 2*7**0
Out: 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 : GF = galois.GF(7)

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

In : p.nonzero_coeffs
Out: 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 : GF = galois.GF(7)

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

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

Type

numpy.ndarray

property string

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

Examples

In : GF = galois.GF(7)

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

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

Type

str