galois.irreducible_poly¶

galois.irreducible_poly(order: int, degree: int, method: 'min' | 'max' | 'random' = 'min') → Poly¶

Returns a monic irreducible polynomial $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.

method: 'min' | 'max' | 'random' = 'min'¶

The search method for finding the irreducible polynomial.

• "min" (default): Returns the lexicographically-minimal monic irreducible polynomial.

• "max": Returns the lexicographically-maximal monic irreducible polynomial.

• "random": Returns a randomly generated degree-$m$ monic irreducible polynomial.

Returns

The degree-$m$ monic irreducible polynomial over $\mathrm{GF}(q)$.

See also

Poly.is_irreducible, primitive_poly, conway_poly

Notes

If $f(x)$ is an irreducible polynomial over $\mathrm{GF}(q)$ and $a\in \mathrm{GF}(q)\mathrm{\setminus }\{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

Search methods

Find the lexicographically-minimal monic irreducible polynomial.

In [1]: galois.irreducible_poly(7, 3)
Out[1]: Poly(x^3 + 2, GF(7))

Find the lexicographically-maximal monic irreducible polynomial.

In [2]: galois.irreducible_poly(7, 3, method="max")
Out[2]: Poly(x^3 + 6x^2 + 6x + 4, GF(7))

Find a random monic irreducible polynomial.

In [3]: galois.irreducible_poly(7, 3, method="random")
Out[3]: Poly(x^3 + 2x^2 + 1, GF(7))

Properties

Find a random monic irreducible polynomial over $\mathrm{GF}(7)$ with degree $5$.

In [4]: f = galois.irreducible_poly(7, 5, method="random"); f
Out[4]: Poly(x^5 + 6x^3 + 2x^2 + 2x + 4, GF(7))

In [5]: f.is_irreducible()
Out[5]: True

Monic irreducible polynomials scaled by non-zero field elements (now non-monic) are also irreducible.

In [6]: GF = galois.GF(7)

In [7]: g = f * GF(3); g
Out[7]: Poly(3x^5 + 4x^3 + 6x^2 + 6x + 5, GF(7))

In [8]: g.is_irreducible()
Out[8]: True