galois.irreducible_polys(order: int, degree: int, 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.

reverse: bool = False

Indicates to return the irreducible polynomials from lexicographically maximal to minimal. 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))]

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 [2]: 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 [3]: generator = galois.irreducible_polys(3, 4, reverse=True); generator
Out[3]: <generator object irreducible_polys at 0x7fb50ff2b9e0>

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

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

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