-
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
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 0x7fa117c63200> 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))