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 : Literal['min', 'max', 'random']

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

See also

is_irreducible, primitive_poly, conway_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

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

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

In [5]: galois.is_irreducible(f)
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^4 + x^3 + 5x^2 + 4x + 2, GF(7))

In [8]: galois.is_irreducible(g)
Out[8]: True
Last update: Apr 03, 2022