galois.primitive_polys

galois.primitive_polys(order: int, degree: int, reverse: bool = False) Iterator[Poly]

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

Parameters
order: int

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

degree: int

The degree m of the desired primitive polynomial.

reverse: bool = False

Indicates to return the primitive polynomials from lexicographically maximal to minimal. The default is False.

Returns

An iterator over all degree-m monic primitive polynomials over GF(q).

Notes

If f(x) is a primitive polynomial over GF(q) and aGF(q){0}, then af(x) is also primitive.

In addition to other applications, f(x) produces the field extension GF(qm) of GF(q). Since f(x) is primitive, x is a primitive element α of GF(qm) such that GF(qm)={0,1,α,α2,,αqm2}.

Examples

All monic primitive polynomials over 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))]

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

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

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

Last update: May 16, 2022