galois.Poly¶

class galois.Poly(coeffs, field=None, order='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 Polynomial Creation 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 over \(\mathrm{GF}(p^m)\) 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.
`copy`()	Deep copies the polynomial.
`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 Galois field array class 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, field=None, order='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 : Union[Sequence[int], 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 : Optional[galois.FieldClass]

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 : Literal['desc', 'asc']

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, coeffs=None, field=None)¶

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

Parameters

degrees : Union[Sequence[int], numpy.ndarray]

The polynomial degrees with non-zero coefficients.

coeffs : Optional[Union[Sequence[int], numpy.ndarray, galois.FieldArray]]

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 : Optional[galois.FieldClass]

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}(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=<class 'numpy.ndarray over GF(2)'>)¶

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

Parameters

field : Optional[galois.FieldClass]: 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}(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, field=<class 'numpy.ndarray over GF(2)'>)¶

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

galois.Poly.Int() and galois.Poly.__int__() are inverse operations.

Parameters

integer : int: The integer representation of the polynomial \(f(x)\).
field : Optional[galois.FieldClass]: 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

Integer

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

Binary string

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'

Octal string

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'

Hex string

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=<class 'numpy.ndarray over GF(2)'>)¶

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

Parameters

field : Optional[galois.FieldClass]: 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}(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, seed=None, 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.
seed : Optional[Union[int, numpy.random._generator.Generator]]: 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 : Optional[galois.FieldClass]: 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^4 + x^3 + x^2, 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, multiplicities=None, field=None)¶

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

Parameters

roots : Union[Sequence[int], 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 : Optional[Union[Sequence[int], numpy.ndarray]]

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

field : Optional[galois.FieldClass]

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{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, field=<class 'numpy.ndarray over GF(2)'>)¶

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

galois.Poly.Str() and galois.Poly.__str__() are inverse operations.

Parameters

string : str: The string representation of the polynomial \(f(x)\).
field : Optional[galois.FieldClass]: 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]: 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=<class 'numpy.ndarray over GF(2)'>)¶

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

Parameters

field : Optional[galois.FieldClass]: 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}(3^5)\).

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

In [3]: galois.Poly.Zero(GF)
Out[3]: Poly(0, GF(3^5))

__call__(x, field=None, elementwise=True)¶

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

Parameters

x : Union[int, Sequence[int], numpy.ndarray, galois.FieldArray]: An array (or 0-D scalar) \(x\) of finite field elements to evaluate the polynomial at.
field : Optional[galois.FieldClass]: The Galois field to evaluate the polynomial over. The default is None which represents the polynomial’s current field, i.e. field.
elementwise : bool: 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.

Return type

galois.FieldArray

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

Determines if two polynomials over \(\mathrm{GF}(p^m)\) are equal.

Parameters

other : Union[galois.Poly, galois.FieldArray, int]: The polynomial \(b(x)\) or a finite field scalar (equivalently a degree-\(0\) polynomial). An integer may be passed and is interpreted as a degree-\(0\) polynomial in the field \(a(x)\) is over.

Returns

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

Return type

bool

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 scalars is allowed for convenience.

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

In [9]: a = galois.Poly([0], field=GF); a
Out[9]: Poly(0, GF(7))

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

In [11]: a == 0
Out[11]: True

__int__()¶

The integer representation of the polynomial.

galois.Poly.Int() and galois.Poly.__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__()¶

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

Returns: The length of the coefficient array.
Return type: int

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

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

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

galois.Poly.Str() and galois.Poly.__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=None, order='desc')¶

Returns the polynomial coefficients in the order and size specified.

Parameters

size : Optional[int]: 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 : Literal['desc', 'asc']: 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.

Return type

galois.FieldArray

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)

copy()¶

Deep copies the polynomial.

Returns: A copy of the original polynomial.
Return type: galois.Poly

derivative(k=1)¶

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

Parameters

k : int: 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. 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

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

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

In [2]: f.derivative()
Out[2]: Poly(x^6 + x^4 + 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(6x^11 + 2x^10 + 6x^9 + 4x^8 + x^7 + 6x^5 + 4x^4 + 5x^3 + 2x^2 + 4x + 4, GF(7))

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

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

In [8]: f.derivative(3)
Out[8]: Poly(4x^8 + 5x^7 + 3x^2 + 5x + 2, 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(71x^7 + 100x^6 + 165x^5 + 238x^4 + 202x^3 + 217x^2 + 43x + 142, GF(3^5))

In [12]: f.derivative()
Out[12]: Poly(71x^6 + 87x^4 + 238x^3 + 110x + 43, GF(3^5))

In [13]: f.derivative(2)
Out[13]: Poly(87x^3 + 110, 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()¶

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.
numpy.ndarray – 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}\]

References

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

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 : galois.FieldArray¶

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)

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

property field : galois.FieldClass¶

The Galois field array class for the finite field the coefficients are over.

Examples

In [1]: a = galois.Poly.Random(5); a
Out[1]: Poly(x^5 + x^3 + x^2, 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(66x^5 + 135x^4 + 25x^3 + 214x^2 + 57x + 102, GF(2^8))

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

property nonzero_coeffs : galois.FieldArray¶

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)

property nonzero_degrees : numpy.ndarray¶

An array of the polynomial degrees that have non-zero coefficients in 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])

Last update: Apr 03, 2022