galois.irreducible_polys(order: int, degree: int, terms: int | str | None = None, reverse: bool = False) → Iterator[Poly]

Iterates through all monic irreducible 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 irreducible 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 irreducible polynomials from lexicographically last to first. The default is False.

Returns:

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

See also

Poly.is_irreducible, primitive_polys

Notes

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

In addition to other applications, \(f(x)\) produces the field extension \(\mathrm{GF}(q^m)\) of \(\mathrm{GF}(q)\).

Examples

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

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

Find all monic irreducible polynomials with four terms.

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

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

In [3]: list(galois.irreducible_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^2 + 2, GF(3)),
 Poly(x^4 + 2x^2 + 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.irreducible_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 + 2x + 1
x^4 + 2x^3 + x^2 + x + 2
x^4 + 2x^3 + x^2 + 1
x^4 + 2x^3 + x + 1
x^4 + 2x^3 + 2

Or, manually iterate over the generator.

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

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

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