galois.Poly¶

class galois.Poly(coeffs: ArrayLike, field: type[Array] | None = None, order: '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)\).
distinct_degree_factors()	Factors the monic, square-free polynomial \(f(x)\) into a product of polynomials whose irreducible factors all have the same degree.
equal_degree_factors(degree)	Factors the monic, square-free polynomial \(f(x)\) of degree \(rd\) into a product of \(r\) irreducible factors with degree \(d\).
factors()	Computes the irreducible factors of the non-constant, monic polynomial \(f(x)\).
is_irreducible()	Determines whether the polynomial \(f(x)\) over \(\mathrm{GF}(p^m)\) is irreducible.
is_primitive()	Determines whether the polynomial \(f(x)\) over \(\mathrm{GF}(q)\) is primitive.
is_square_free()	Determines whether the polynomial \(f(x)\) over \(\mathrm{GF}(q)\) is square-free.
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\).
square_free_factors()	Factors the monic polynomial \(f(x)\) into a product of square-free polynomials.

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.
is_monic	Returns whether the polynomial is monic, meaning its highest-degree coefficient is one.
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: '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: ArrayLike¶

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

field: type[Array] | None = None¶

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: 'desc' | 'asc' = 'desc'¶

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: Sequence[int] | ndarray¶

The polynomial degrees with non-zero coefficients.

coeffs: ArrayLike | None = None¶

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

field: type[Array] | None = None¶

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: type[Array] | None = None¶

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: int¶

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

field: type[Array] | None = None¶

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

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: type[Array] | None = None) → Poly¶

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

Parameters

field: type[Array] | None = None¶

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: int¶

The degree of the polynomial.

seed: int | Generator | None = None¶

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: type[Array] | None = None¶

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 + 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: ArrayLike¶

The roots of the desired polynomial.

multiplicities: Sequence[int] | ndarray | None = None¶

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

field: type[Array] | None = None¶

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: str¶

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

field: type[Array] | None = None¶

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: type[Array] | None = None¶

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: ElementLike | ArrayLike¶

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

field: type[Array] | None = None¶

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

elementwise: bool = True¶

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: PolyLike¶

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.

Tip

Use set_printoptions() to display the polynomial coefficients in degree-ascending order.

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.

Tip

Use set_printoptions() to display the polynomial coefficients in degree-ascending order.

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: 'desc' | 'asc' = 'desc') → Array¶

Returns the polynomial coefficients in the order and size specified.

Parameters

size: int | None = None¶

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: 'desc' | 'asc' = 'desc'¶

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: int = 1¶

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

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

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

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

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

In [8]: f.derivative(3)
Out[8]: Poly(x^8 + 4x^7 + x^3 + x^2 + 6x + 5, 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(183x^7 + 242x^6 + 229x^5 + 195x^4 + 53x^3 + 92x^2 + x + 193, GF(3^5))

In [12]: f.derivative()
Out[12]: Poly(183x^6 + 134x^4 + 195x^3 + 181x + 1, GF(3^5))

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

distinct_degree_factors() → tuple[list[Poly], list[int]]¶

Factors the monic, square-free polynomial \(f(x)\) into a product of polynomials whose irreducible factors all have the same degree.

Returns

• The list of polynomials \(f_i(x)\) whose irreducible factors all have degree \(i\).

• The list of corresponding distinct degrees \(i\).

Raises

ValueError – If \(f(x)\) is not monic, has degree 0, or is not square-free.

Notes

The Distinct-Degree Factorization algorithm factors a square-free polynomial \(f(x)\) with degree \(d\) into a product of \(d\) polynomials \(f_i(x)\), where \(f_i(x)\) is the product of all irreducible factors of \(f(x)\) with degree \(i\).

\[f(x) = \prod_{i=1}^{d} f_i(x)\]

For example, suppose \(f(x) = x(x + 1)(x^2 + x + 1)(x^3 + x + 1)(x^3 + x^2 + 1)\) over \(\mathrm{GF}(2)\), then the distinct-degree factorization is

\[\begin{split}f_1(x) &= x(x + 1) = x^2 + x \\ f_2(x) &= x^2 + x + 1 \\ f_3(x) &= (x^3 + x + 1)(x^3 + x^2 + 1) = x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 \\ f_i(x) &= 1\ \textrm{for}\ i = 4, \dots, 10.\end{split}\]

Some \(f_i(x) = 1\), but those polynomials are not returned by this function. In this example, the function returns \(\{f_1(x), f_2(x), f_3(x)\}\) and \(\{1, 2, 3\}\).

The Distinct-Degree Factorization algorithm is often applied after the Square-Free Factorization algorithm, see square_free_factors(). A complete polynomial factorization is implemented in factors().

References

• Hachenberger, D. and Jungnickel, D. Topics in Galois Fields. Algorithm 6.2.2.

• Section 2.2 from https://people.csail.mit.edu/dmoshkov/courses/codes/poly-factorization.pdf

Examples

From the example in the notes, suppose \(f(x) = x(x + 1)(x^2 + x + 1)(x^3 + x + 1)(x^3 + x^2 + 1)\) over \(\mathrm{GF}(2)\).

In [1]: a = galois.Poly([1, 0]); a, a.is_irreducible()
Out[1]: (Poly(x, GF(2)), True)

In [2]: b = galois.Poly([1, 1]); b, b.is_irreducible()
Out[2]: (Poly(x + 1, GF(2)), True)

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

In [4]: d = galois.Poly([1, 0, 1, 1]); d, d.is_irreducible()
Out[4]: (Poly(x^3 + x + 1, GF(2)), True)

In [5]: e = galois.Poly([1, 1, 0, 1]); e, e.is_irreducible()
Out[5]: (Poly(x^3 + x^2 + 1, GF(2)), True)

In [6]: f = a * b * c * d * e; f
Out[6]: Poly(x^10 + x^9 + x^8 + x^3 + x^2 + x, GF(2))

The distinct-degree factorization is \(\{x(x + 1), x^2 + x + 1, (x^3 + x + 1)(x^3 + x^2 + 1)\}\) whose irreducible factors have degrees \(\{1, 2, 3\}\).

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

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

equal_degree_factors(degree: int) → list[Poly]¶

Factors the monic, square-free polynomial \(f(x)\) of degree \(rd\) into a product of \(r\) irreducible factors with degree \(d\).

Parameters

degree: int¶

The degree \(d\) of each irreducible factor of \(f(x)\).

Returns

The list of \(r\) irreducible factors \(\{g_1(x), \dots, g_r(x)\}\) in lexicographically-increasing order.

Raises

ValueError – If \(f(x)\) is not monic, has degree 0, or is not square-free.

Notes

The Equal-Degree Factorization algorithm factors a square-free polynomial \(f(x)\) with degree \(rd\) into a product of \(r\) irreducible polynomials each with degree \(d\). This function implements the Cantor-Zassenhaus algorithm, which is probabilistic.

The Equal-Degree Factorization algorithm is often applied after the Distinct-Degree Factorization algorithm, see distinct_degree_factors(). A complete polynomial factorization is implemented in factors().

References

• Section 2.3 from https://people.csail.mit.edu/dmoshkov/courses/codes/poly-factorization.pdf

• Section 1 from https://www.csa.iisc.ac.in/~chandan/courses/CNT/notes/lec8.pdf

Examples

Factor a product of degree-1 irreducible polynomials over \(\mathrm{GF}(2)\).

In [1]: a = galois.Poly([1, 0]); a, a.is_irreducible()
Out[1]: (Poly(x, GF(2)), True)

In [2]: b = galois.Poly([1, 1]); b, b.is_irreducible()
Out[2]: (Poly(x + 1, GF(2)), True)

In [3]: f = a * b; f
Out[3]: Poly(x^2 + x, GF(2))

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

Factor a product of degree-3 irreducible polynomials over \(\mathrm{GF}(5)\).

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

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

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

In [8]: f = a * b; f
Out[8]: Poly(x^6 + 4x^5 + x^4 + 3x^3 + 2x^2 + 2x + 4, GF(5))

In [9]: f.equal_degree_factors(3)
Out[9]: [Poly(x^3 + 2x + 1, GF(5)), Poly(x^3 + 4x^2 + 4x + 4, GF(5))]

factors() → tuple[list[Poly], list[int]]¶

Computes the irreducible factors of the non-constant, monic polynomial \(f(x)\).

Returns

• Sorted list of irreducible factors \(\{g_1(x), g_2(x), \dots, g_k(x)\}\) of \(f(x)\) sorted in lexicographically-increasing order.

• List of corresponding multiplicities \(\{e_1, e_2, \dots, e_k\}\).

Raises

ValueError – If \(f(x)\) is not monic or has degree 0.

Notes

This function factors a monic polynomial \(f(x)\) into its \(k\) irreducible factors such that \(f(x) = g_1(x)^{e_1} g_2(x)^{e_2} \dots g_k(x)^{e_k}\).

Steps:

1. Apply the Square-Free Factorization algorithm to factor the monic polynomial into square-free polynomials.

2. Apply the Distinct-Degree Factorization algorithm to factor each square-free polynomial into a product of factors with the same degree.

3. Apply the Equal-Degree Factorization algorithm to factor the product of factors of equal degree into their irreducible factors.

References

• Hachenberger, D. and Jungnickel, D. Topics in Galois Fields. Algorithm 6.1.7.

• Section 2.1 from https://people.csail.mit.edu/dmoshkov/courses/codes/poly-factorization.pdf

Examples

Generate irreducible polynomials over \(\mathrm{GF}(3)\).

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

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

In [3]: g2 = galois.irreducible_poly(3, 4); g2
Out[3]: Poly(x^4 + x + 2, GF(3))

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

Construct a composite polynomial.

In [5]: e1, e2, e3 = 5, 4, 3

In [6]: f = g1**e1 * g2**e2 * g3**e3; f
Out[6]: Poly(x^46 + x^44 + 2x^41 + x^40 + 2x^39 + 2x^38 + 2x^37 + 2x^36 + 2x^34 + x^33 + 2x^32 + x^31 + 2x^30 + 2x^29 + 2x^28 + 2x^25 + 2x^24 + 2x^23 + x^20 + x^19 + x^18 + x^15 + 2x^10 + 2x^8 + x^5 + x^4 + x^3 + 1, GF(3))

Factor the polynomial into its irreducible factors over \(\mathrm{GF}(3)\).

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

is_irreducible() → bool¶

Determines whether the polynomial \(f(x)\) over \(\mathrm{GF}(p^m)\) is irreducible.

Returns

True if the polynomial is irreducible.

Important

This is a method, not a property, to indicate this test is computationally expensive.

See also

irreducible_poly, irreducible_polys

Notes

A polynomial \(f(x) \in \mathrm{GF}(p^m)[x]\) is reducible over \(\mathrm{GF}(p^m)\) if it can be represented as \(f(x) = g(x) h(x)\) for some \(g(x), h(x) \in \mathrm{GF}(p^m)[x]\) of strictly lower degree. If \(f(x)\) is not reducible, it is said to be irreducible. Since Galois fields are not algebraically closed, such irreducible polynomials exist.

This function implements Rabin’s irreducibility test. It says a degree-\(m\) polynomial \(f(x)\) over \(\mathrm{GF}(q)\) for prime power \(q\) is irreducible if and only if \(f(x)\ |\ (x^{q^m} - x)\) and \(\textrm{gcd}(f(x),\ x^{q^{m_i}} - x) = 1\) for \(1 \le i \le k\), where \(m_i = m/p_i\) for the \(k\) prime divisors \(p_i\) of \(m\).

References

• Rabin, M. Probabilistic algorithms in finite fields. SIAM Journal on Computing (1980), 273-280. https://apps.dtic.mil/sti/pdfs/ADA078416.pdf

• Gao, S. and Panarino, D. Tests and constructions of irreducible polynomials over finite fields. https://www.math.clemson.edu/~sgao/papers/GP97a.pdf

• Section 4.5.1 from https://cacr.uwaterloo.ca/hac/about/chap4.pdf

• https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields

Examples

# Conway polynomials are always irreducible (and primitive)
In [1]: f = galois.conway_poly(2, 5); f
Out[1]: Poly(x^5 + x^2 + 1, GF(2))

# f(x) has no roots in GF(2), a necessary but not sufficient condition of being irreducible
In [2]: f.roots()
Out[2]: GF([], order=2)

In [3]: f.is_irreducible()
Out[3]: True

In [4]: g = galois.irreducible_poly(2**4, 2, method="random"); g
Out[4]: Poly(x^2 + 14x + 7, GF(2^4))

In [5]: h = galois.irreducible_poly(2**4, 3, method="random"); h
Out[5]: Poly(x^3 + 13x^2 + 7x + 9, GF(2^4))

In [6]: f = g * h; f
Out[6]: Poly(x^5 + 3x^4 + 10x^3 + x + 10, GF(2^4))

In [7]: f.is_irreducible()
Out[7]: False

is_primitive() → bool¶

Determines whether the polynomial \(f(x)\) over \(\mathrm{GF}(q)\) is primitive.

Returns

True if the polynomial is primitive.

Important

This is a method, not a property, to indicate this test is computationally expensive.

See also

primitive_poly, primitive_polys, conway_poly, matlab_primitive_poly

Notes

A degree-\(m\) polynomial \(f(x)\) over \(\mathrm{GF}(q)\) is primitive if it is irreducible and \(f(x)\ |\ (x^k - 1)\) for \(k = q^m - 1\) and no \(k\) less than \(q^m - 1\).

References

• Algorithm 4.77 from https://cacr.uwaterloo.ca/hac/about/chap4.pdf

Examples

All Conway polynomials are primitive.

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

In [2]: f.is_primitive()
Out[2]: True

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

In [4]: f.is_primitive()
Out[4]: True

The irreducible polynomial of \(\mathrm{GF}(2^8)\) for AES is not primitive.

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

In [6]: f.is_irreducible()
Out[6]: True

In [7]: f.is_primitive()
Out[7]: False

is_square_free() → bool¶

Determines whether the polynomial \(f(x)\) over \(\mathrm{GF}(q)\) is square-free.

Returns

True if the polynomial is square-free.

Important

This is a method, not a property, to indicate this test is computationally expensive.

Notes

A square-free polynomial \(f(x)\) has no irreducible factors with multiplicity greater than one. Therefore, its canonical factorization is

\[f(x) = \prod_{i=1}^{k} g_i(x)^{e_i} = \prod_{i=1}^{k} g_i(x) .\]

Examples

Generate irreducible polynomials over \(\mathrm{GF}(3)\).

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

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

In [3]: f2 = galois.irreducible_poly(3, 4); f2
Out[3]: Poly(x^4 + x + 2, GF(3))

Determine if composite polynomials are square-free over \(\mathrm{GF}(3)\).

In [4]: (f1 * f2).is_square_free()
Out[4]: True

In [5]: (f1**2 * f2).is_square_free()
Out[5]: False

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: False = False) → Array¶

roots(multiplicity: True) → tuple[Array, ndarray]

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

Parameters

multiplicity: False = False¶

multiplicity: True

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

square_free_factors() → tuple[list[Poly], list[int]]¶

Factors the monic polynomial \(f(x)\) into a product of square-free polynomials.

Returns

• The list of non-constant, square-free polynomials \(h_j(x)\) in the factorization.

• The list of corresponding multiplicities \(j\).

Raises

ValueError – If \(f(x)\) is not monic or has degree 0.

Notes

The Square-Free Factorization algorithm factors \(f(x)\) into a product of \(m\) square-free polynomials \(h_j(x)\) with multiplicity \(j\).

\[f(x) = \prod_{j=1}^{m} h_j(x)^j\]

Some \(h_j(x) = 1\), but those polynomials are not returned by this function.

A complete polynomial factorization is implemented in factors().

References

• Hachenberger, D. and Jungnickel, D. Topics in Galois Fields. Algorithm 6.1.7.

• Section 2.1 from https://people.csail.mit.edu/dmoshkov/courses/codes/poly-factorization.pdf

Examples

Suppose \(f(x) = x(x^3 + 2x + 4)(x^2 + 4x + 1)^3\) over \(\mathrm{GF}(5)\). Each polynomial \(x\), \(x^3 + 2x + 4\), and \(x^2 + 4x + 1\) are all irreducible over \(\mathrm{GF}(5)\).

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

In [2]: a = galois.Poly([1,0], field=GF); a, a.is_irreducible()
Out[2]: (Poly(x, GF(5)), True)

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

In [4]: c = galois.Poly([1,4,1], field=GF); c, c.is_irreducible()
Out[4]: (Poly(x^2 + 4x + 1, GF(5)), True)

In [5]: f = a * b * c**3; f
Out[5]: Poly(x^10 + 2x^9 + 3x^8 + x^7 + x^6 + 2x^5 + 3x^3 + 4x, GF(5))

The square-free factorization is \(\{x(x^3 + 2x + 4), x^2 + 4x + 1\}\) with multiplicities \(\{1, 3\}\).

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

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

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 : 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^2 + 1, 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(142x^5 + 74x^4 + 124x^3 + 196x^2 + 254x + 132, GF(2^8))

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

property is_monic : bool¶

Returns whether the polynomial is monic, meaning its highest-degree coefficient is one.

Examples

A monic polynomial over \(\mathrm{GF}(7)\).

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

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

In [3]: p.is_monic
Out[3]: True

A non-monic polynomial over \(\mathrm{GF}(7)\).

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

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

In [6]: p.is_monic
Out[6]: False

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