galois.Poly

class galois.Poly(coeffs: ArrayLike, field: Type[Array] | None = None, order: Literal['desc', 'asc'] = 'desc')

A univariate polynomial \(f(x)\) over \(\mathrm{GF}(p^m)\).

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))

Create a polynomial over \(\mathrm{GF}(3^5)\).

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

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

See Polynomials and Polynomial Arithmetic for more examples.

Constructors

__init__(coeffs[, field, order])

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

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)\).

Int(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[, seed, 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.

Str(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)\).

Special Methods

__call__(x[, field, elementwise])

Evaluates the polynomial \(f(x)\) at x.

__eq__(other)

Determines if two polynomials are equal.

__int__()

The integer representation of the polynomial.

__len__()

Returns the length of the coefficient array Poly.degree + 1.

__repr__()

A representation of the polynomial and the finite field it's over.

__str__()

The string representation of the polynomial, without specifying the finite field it's over.

Methods

coefficients([size, order])

Returns the polynomial coefficients in the order and size specified.

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()

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.

degrees

An array of the polynomial degrees in descending order.

field

The Array subclass for the finite field the coefficients are over.

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 descending order.

__init__(coeffs: ArrayLike, field: Type[Array] | None = None, order: Literal['desc', 'asc'] = 'desc')

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

Parameters
coeffs

The polynomial coefficients \(\{a_d, a_{d-1}, \dots, a_1, a_0\}\).

field

The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over.

  • None (default): If the coefficients are a Array, 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).

  • Array subclass: The coefficients are explicitly converted to this Galois field field(coeffs).

order

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\}\).

classmethod Degrees(degrees: Sequence[int] | ndarray, coeffs: ArrayLike | None = None, field: Type[Array] | None = None) Poly

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

Parameters
degrees

The polynomial degrees with non-zero coefficients.

coeffs

The corresponding non-zero polynomial coefficients. The default is None which corresponds to all ones.

field

The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over.

  • None (default): If the coefficients are a Array, 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).

  • Array subclass: The coefficients are explicitly converted to this Galois field field(coeffs).

Returns

The polynomial \(f(x)\).

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}(3^5)\) by specifying the degrees with non-zero coefficients.

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

In [3]: galois.Poly.Degrees([3, 1, 0], coeffs=[214, 73, 185], field=GF)
Out[3]: Poly(214x^3 + 73x + 185, GF(3^5))
classmethod Identity(field: Type[Array] | None = None) Poly

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

Parameters
field

The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is None which corresponds to GF2.

Returns

The polynomial \(f(x) = x\).

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}(3^5)\).

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

In [3]: galois.Poly.Identity(GF)
Out[3]: Poly(x, GF(3^5))
classmethod Int(integer: int, field: Type[Array] | None = None) Poly

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

Int() and __int__() are inverse operations.

Parameters
integer

The integer representation of the polynomial \(f(x)\).

field

The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is None which corresponds to GF2.

Returns

The polynomial \(f(x)\).

Examples

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

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

In [2]: int(f)
Out[2]: 5

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

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

In [4]: f = galois.Poly.Int(186535908, field=GF); f
Out[4]: Poly(13x^3 + 117, GF(3^5))

In [5]: int(f)
Out[5]: 186535908

# The polynomial/integer equivalence
In [6]: int(f) == 13*GF.order**3 + 117
Out[6]: True

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

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

In [8]: bin(f)
Out[8]: '0b1011'

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

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

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

In [11]: oct(f)
Out[11]: '0o5034'

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

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

In [13]: f = galois.Poly.Int(int("0xf700a275", 16), field=GF); f
Out[13]: Poly(247x^3 + 162x + 117, GF(2^8))

In [14]: hex(f)
Out[14]: '0xf700a275'
classmethod One(field: Type[Array] | None = None) Poly

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

Parameters
field

The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is None which corresponds to GF2.

Returns

The polynomial \(f(x) = 1\).

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}(3^5)\).

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

In [3]: galois.Poly.One(GF)
Out[3]: Poly(1, GF(3^5))
classmethod Random(degree: int, seed: int | Generator | None = None, field: Type[Array] | None = None) Poly

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

Parameters
degree

The degree of the polynomial.

seed

Non-negative integer used to initialize the PRNG. The default is None which means that unpredictable entropy will be pulled from the OS to be used as the seed. A numpy.random.Generator can also be passed.

field

The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is None which corresponds to GF2.

Returns

The polynomial \(f(x)\).

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^2 + x + 1, GF(2))

Construct a random degree-\(5\) polynomial over \(\mathrm{GF}(3^5)\) with a given seed. This produces repeatable results.

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

In [3]: galois.Poly.Random(5, seed=123456789, field=GF)
Out[3]: Poly(56x^5 + 228x^4 + 157x^3 + 218x^2 + 148x + 43, GF(3^5))

In [4]: galois.Poly.Random(5, seed=123456789, field=GF)
Out[4]: Poly(56x^5 + 228x^4 + 157x^3 + 218x^2 + 148x + 43, GF(3^5))

Construct multiple polynomials with one global seed.

In [5]: rng = np.random.default_rng(123456789)

In [6]: galois.Poly.Random(5, seed=rng, field=GF)
Out[6]: Poly(56x^5 + 228x^4 + 157x^3 + 218x^2 + 148x + 43, GF(3^5))

In [7]: galois.Poly.Random(5, seed=rng, field=GF)
Out[7]: Poly(194x^5 + 195x^4 + 200x^3 + 141x^2 + 164x + 119, GF(3^5))
classmethod Roots(roots: ArrayLike, multiplicities: Sequence[int] | ndarray | None = None, field: Type[Array] | None = None) Poly

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

Parameters
roots

The roots of the desired polynomial.

multiplicities

The corresponding root multiplicities. The default is None which corresponds to all ones.

field

The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over.

  • None (default): If the roots are a Array, 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).

  • Array subclass: The roots are explicitly converted to this Galois field field(roots).

Returns

The polynomial \(f(x)\).

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{split}f(x) &= (x - r_1)^{m_1} (x - r_2)^{m_2} \dots (x - r_k)^{m_k} \\ &= a_d x^d + a_{d-1} x^{d-1} + \dots + a_1 x + a_0\end{split}\]

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]: f = galois.Poly.Roots(roots); f
Out[2]: Poly(x^3 + x^2, GF(2))

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

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

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

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

In [6]: f = galois.Poly.Roots(roots, multiplicities=[1, 2, 1], field=GF); f
Out[6]: Poly(x^4 + 215x^3 + 90x^2 + 183x + 119, GF(3^5))

# Evaluate the polynomial at its roots
In [7]: f(roots)
Out[7]: GF([0, 0, 0], order=3^5)
classmethod Str(string: str, field: Type[Array] | None = None) Poly

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

Str() and __str__() are inverse operations.

Parameters
string

The string representation of the polynomial \(f(x)\).

field

The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is None which corresponds to GF2.

Returns

The polynomial \(f(x)\).

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]: f = galois.Poly.Str("x^2 + 1"); f
Out[1]: Poly(x^2 + 1, GF(2))

In [2]: str(f)
Out[2]: 'x^2 + 1'

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

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

In [4]: f = galois.Poly.Str("13x^3 + 117", field=GF); f
Out[4]: Poly(13x^3 + 117, GF(3^5))

In [5]: str(f)
Out[5]: '13x^3 + 117'
classmethod Zero(field: Type[Array] | None = None) Poly

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

Parameters
field

The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is None which corresponds to GF2.

Returns

The polynomial \(f(x) = 0\).

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}(3^5)\).

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

In [3]: galois.Poly.Zero(GF)
Out[3]: Poly(0, GF(3^5))
__call__(x: ElementLike | ArrayLike, field: Type[Array] | None = None, elementwise: bool = True) Array

Evaluates the polynomial \(f(x)\) at x.

Parameters
x

A finite field scalar or array to evaluate the polynomial at.

field

The Galois field to evaluate the polynomial over. The default is None which represents the polynomial’s current field, i.e. field.

elementwise

Indicates whether to evaluate \(x\) elementwise. The default is True. If False (only valid for square matrices), the polynomial indeterminate \(x\) is exponentiated using matrix powers (repeated matrix multiplication).

Returns

The result of the polynomial evaluation \(f(x)\). The resulting array has the same shape as x.

Examples

Create a polynomial over \(\mathrm{GF}(3^5)\).

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

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

Evaluate the polynomial elementwise at \(x\).

In [3]: x = GF([185, 218, 84, 163]); x
Out[3]: GF([185, 218,  84, 163], order=3^5)

In [4]: f(x)
Out[4]: GF([ 33, 163, 146,  96], order=3^5)

# The equivalent calculation
In [5]: GF(37)*x**3 + GF(123)*x**2 + GF(201)
Out[5]: GF([ 33, 163, 146,  96], order=3^5)

Evaluate the polynomial at the square matrix \(X\).

In [6]: X = GF([[185, 218], [84, 163]]); X
Out[6]: 
GF([[185, 218],
    [ 84, 163]], order=3^5)

In [7]: f(X, elementwise=False)
Out[7]: 
GF([[103, 192],
    [156,  10]], order=3^5)

# The equivalent calculation
In [8]: GF(37)*np.linalg.matrix_power(X,3) + GF(123)*np.linalg.matrix_power(X,2) + GF(201)*GF.Identity(2)
Out[8]: 
GF([[103, 192],
    [156,  10]], order=3^5)
__eq__(other: PolyLike) bool

Determines if two polynomials are equal.

Parameters
other

The polynomial to compare against.

Returns

True if the two polynomials have the same coefficients and are over the same finite field.

Examples

Compare two polynomials over the same field.

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

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

In [3]: a == b
Out[3]: True

# They are still two distinct objects, however
In [4]: a is b
Out[4]: False

Compare two polynomials with the same coefficients but over different fields.

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

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

In [7]: a == b
Out[7]: False

Comparison with PolyLike objects is allowed for convenience.

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

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

In [10]: a == GF([3, 0, 2])
Out[10]: True

In [11]: a == [3, 0, 2]
Out[11]: True

In [12]: a == "3x^2 + 2"
Out[12]: True

In [13]: a == 3*7**2 + 2
Out[13]: True
__int__() int

The integer representation of the polynomial.

Int() and __int__() are inverse operations.

Notes

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, the polynomial coefficients \(\{a_d, a_{d-1}, \dots, a_1, a_0\}\) are considered as the \(d\) “digits” of a radix-\(p^m\) value. The polynomial’s integer representation is that value in decimal (radix-\(10\)).

Examples

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

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

In [3]: int(f)
Out[3]: 1066

In [4]: int(f) == 3*GF.order**3 + 5*GF.order**1 + 2*GF.order**0
Out[4]: True
__len__() int

Returns the length of the coefficient array Poly.degree + 1.

Returns

The length of the coefficient array.

Examples

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

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

In [3]: f.coeffs
Out[3]: GF([ 37, 123,   0, 201], order=3^5)

In [4]: len(f)
Out[4]: 4

In [5]: f.degree + 1
Out[5]: 4
__repr__() str

A representation of the polynomial and the finite field it’s over.

Examples

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

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

In [3]: f
Out[3]: Poly(3x^3 + 5x + 2, GF(7))
__str__() str

The string representation of the polynomial, without specifying the finite field it’s over.

Str() and __str__() are inverse operations.

Examples

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

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

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

In [4]: print(f)
3x^3 + 5x + 2
coefficients(size: int | None = None, order: Literal['desc', 'asc'] = 'desc') Array

Returns the polynomial coefficients in the order and size specified.

Parameters
size

The fixed size of the coefficient array. Zeros will be added for higher-order terms. This value must be at least degree + 1 or a ValueError will be raised. The default is None which corresponds to degree + 1.

order

The order of the coefficient degrees, either descending (default) or ascending.

Returns

An array of the polynomial coefficients with length size, either in descending order or ascending order.

Notes

This accessor is similar to the coeffs property, but it has more settings. By default, Poly.coeffs == Poly.coefficients().

Examples

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

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

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

In [4]: f.coefficients()
Out[4]: GF([3, 0, 5, 2], order=7)

# Return the coefficients in ascending order
In [5]: f.coefficients(order="asc")
Out[5]: GF([2, 5, 0, 3], order=7)

# Return the coefficients in ascending order with size 8
In [6]: f.coefficients(8, order="asc")
Out[6]: GF([2, 5, 0, 3, 0, 0, 0, 0], order=7)
derivative(k: int = 1) Poly

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

Parameters
k

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)\).

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. The exponent that is “brought down” and multiplied by the coefficient is an integer, not a finite field element. For example, \(3 \cdot a = a + a + a\).

References

Examples

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

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

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

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

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

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

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

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

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

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

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

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

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

In [11]: f = galois.Poly.Random(7, field=GF); f
Out[11]: Poly(193x^7 + 36x^6 + 239x^5 + 167x^4 + 220x^3 + 154x^2 + 31x + 192, GF(3^5))

In [12]: f.derivative()
Out[12]: Poly(193x^6 + 124x^4 + 167x^3 + 200x + 31, GF(3^5))

In [13]: f.derivative(2)
Out[13]: Poly(124x^3 + 200, GF(3^5))

# p derivatives of a polynomial, where p is the field's characteristic, will always result in 0
In [14]: f.derivative(GF.characteristic)
Out[14]: Poly(0, GF(3^5))
reverse() Poly

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})\).

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: Literal[False] = False) Array
roots(multiplicity: Literal[True]) Tuple[Array, ndarray]

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

Parameters
multiplicity

Optionally return the multiplicity of each root. The default is False which only returns the unique roots.

Returns

  • An array of roots of \(f(x)\). The roots are ordered in increasing order.

  • The multiplicity of each root. This is 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{split}f(\alpha^i) &= a_{d}(\alpha^i)^{d} + a_{d-1}(\alpha^i)^{d-1} + \dots + a_1(\alpha^i) + a_0 \\ &\overset{\Delta}{=} \lambda_{i,d} + \lambda_{i,d-1} + \dots + \lambda_{i,1} + \lambda_{i,0} \\ &= \sum_{j=0}^{d} \lambda_{i,j}\end{split}\]

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

\[\begin{split}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 \\ &= 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 \\ &= \lambda_{i,d}\alpha^d + \lambda_{i,d-1}\alpha^{d-1} + \dots + \lambda_{i,1}\alpha + \lambda_{i,0} \\ &= \sum_{j=0}^{d} \lambda_{i,j}\alpha^j\end{split}\]

Examples

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

In [1]: f = galois.Poly.Roots([1, 0], multiplicities=[7, 3]); f
Out[1]: Poly(x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3, GF(2))

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

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

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

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

In [5]: f = galois.Poly.Roots([18, 227, 153], multiplicities=[5, 7, 3], field=GF); f
Out[5]: Poly(x^15 + 118x^14 + 172x^13 + 50x^12 + 204x^11 + 202x^10 + 141x^9 + 153x^8 + 107x^7 + 187x^6 + 66x^5 + 221x^4 + 114x^3 + 121x^2 + 226x + 13, GF(3^5))

In [6]: f.roots()
Out[6]: GF([ 18, 153, 227], order=3^5)

In [7]: f.roots(multiplicity=True)
Out[7]: (GF([ 18, 153, 227], order=3^5), array([5, 3, 7]))
property coeffs : Array

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

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)
property degree : int

The degree of the polynomial. The degree of a polynomial is the highest degree with a 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
property degrees : numpy.ndarray

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

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])
property field : Type[Array]

The Array subclass for the finite field the coefficients are over.

Examples

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

In [2]: a.field
Out[2]: galois.GF2
In [3]: GF = galois.GF(2**8)

In [4]: b = galois.Poly.Random(5, field=GF); b
Out[4]: Poly(116x^5 + 44x^4 + 209x^3 + 224x^2 + 139x + 190, GF(2^8))

In [5]: b.field
Out[5]: galois.GF(2^8)
property nonzero_coeffs : Array

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

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)
property nonzero_degrees : numpy.ndarray

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

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])

Last update: May 11, 2022