Iterates through all monic primitive polynomials \(f(x)\) over \(\mathrm{GF}(q)\) with degree \(m\).

Parameters:¶

order: int¶

The prime power order \(q\) of the field \(\mathrm{GF}(q)\) that the polynomial is over.

degree: int¶

The degree \(m\) of the desired primitive polynomial.

terms: int | str | None = None¶

The desired number of non-zero terms \(t\) in the polynomial.

• None (default): Disregards the number of terms while searching for the polynomial.

• int: The exact number of non-zero terms in the polynomial.

• "min": The minimum possible number of non-zero terms.

reverse: bool = False¶

Indicates to return the primitive polynomials from lexicographically last to first. The default is False.

Returns:¶

An iterator over all degree-\(m\) monic primitive polynomials over \(\mathrm{GF}(q)\).

Notes¶

If \(f(x)\) is a primitive polynomial over \(\mathrm{GF}(q)\) and \(a \in \mathrm{GF}(q) \backslash \{0\}\), then \(a \cdot f(x)\) is also primitive.

In addition to other applications, \(f(x)\) produces the field extension \(\mathrm{GF}(q^m)\) of \(\mathrm{GF}(q)\). Since \(f(x)\) is primitive, \(x\) is a primitive element \(\alpha\) of \(\mathrm{GF}(q^m)\) such that \(\mathrm{GF}(q^m) = \{0, 1, \alpha, \alpha^2, \dots, \alpha^{q^m-2}\}\).

Examples¶

Find all monic primitive polynomials over \(\mathrm{GF}(3)\) with degree 4. You may also use tuple() on the returned generator.

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

Find all monic primitive polynomials with five terms.

In [2]: list(galois.primitive_polys(3, 4, terms=5))
Out[2]: 
[Poly(x^4 + x^3 + x^2 + 2x + 2, GF(3)),
 Poly(x^4 + x^3 + 2x^2 + 2x + 2, GF(3)),
 Poly(x^4 + 2x^3 + x^2 + x + 2, GF(3)),
 Poly(x^4 + 2x^3 + 2x^2 + x + 2, GF(3))]

Find all monic primitive polynomials with the minimum number of non-zero terms.

In [3]: list(galois.primitive_polys(3, 4, terms="min"))
Out[3]: 
[Poly(x^4 + x + 2, GF(3)),
 Poly(x^4 + 2x + 2, GF(3)),
 Poly(x^4 + x^3 + 2, GF(3)),
 Poly(x^4 + 2x^3 + 2, GF(3))]

Loop over all the polynomials in reversed order, only finding them as needed. The search cost for the polynomials that would have been found after the break condition is never incurred.

In [4]: for poly in galois.primitive_polys(3, 4, reverse=True):
   ...:     if poly.coeffs[1] < 2:  # Early exit condition
   ...:         break
   ...:     print(poly)
   ...: 
x^4 + 2x^3 + 2x^2 + x + 2
x^4 + 2x^3 + x^2 + x + 2
x^4 + 2x^3 + 2

Or, manually iterate over the generator.

In [5]: generator = galois.primitive_polys(3, 4, reverse=True); generator
Out[5]: <generator object primitive_polys at 0x7f357c8195a0>

In [6]: next(generator)
Out[6]: Poly(x^4 + 2x^3 + 2x^2 + x + 2, GF(3))

In [7]: next(generator)
Out[7]: Poly(x^4 + 2x^3 + x^2 + x + 2, GF(3))

In [8]: next(generator)
Out[8]: Poly(x^4 + 2x^3 + 2, GF(3))