# galois.irreducible_poly¶

galois.irreducible_poly(order: int, degree: int, method: Literal['min', 'max', 'random'] = 'min') Poly

Returns a monic irreducible polynomial $$f(x)$$ over $$\mathrm{GF}(q)$$ with degree $$m$$.

Parameters
order

The prime power order $$q$$ of the field $$\mathrm{GF}(q)$$ that the polynomial is over.

degree

The degree $$m$$ of the desired irreducible polynomial.

method

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)$$.

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 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 + 5x^2 + 4x + 2, GF(7))


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

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


Last update: Jul 12, 2022