galois.irreducible_poly

galois.irreducible_poly(order, degree, method='min')

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 (str, optional) –

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

Return type

galois.Poly

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

The lexicographically-minimal, monic irreducible polynomial over \(\mathrm{GF}(7)\) with degree \(5\).

In [1]: p = galois.irreducible_poly(7, 5); p
Out[1]: Poly(x^5 + x + 3, GF(7))

In [2]: galois.is_irreducible(p)
Out[2]: True

Irreducible polynomials scaled by non-zero field elements are also irreducible.

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

In [4]: galois.is_irreducible(p * GF(3))
Out[4]: True

A random, monic irreducible polynomial over \(\mathrm{GF}(7^2)\) with degree \(3\).

In [5]: p = galois.irreducible_poly(7**2, 3, method="random"); p
Out[5]: Poly(x^3 + 2x^2 + 15x + 45, GF(7^2))

In [6]: galois.is_irreducible(p)
Out[6]: True