galois.irreducible_poly

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

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

If \(f(x)\) is an irreducible polynomial over \(\mathrm{GF}(p)\) and \(a \in \mathrm{GF}(p) \backslash \{0\}\), then \(a \cdot f(x)\) is also irreducible.

In addition to other applications, \(f(x)\) produces the field extension \(\mathrm{GF}(p^m)\) of \(\mathrm{GF}(p)\).

Parameters

  • characteristic (int) – The prime characteristic \(p\) of the field \(\mathrm{GF}(p)\) 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}(p)\).

Return type

galois.Poly

Examples

# The lexicographically-minimal irreducible polynomial
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

# The lexicographically-maximal irreducible polynomial
In [3]: p = galois.irreducible_poly(7, 5, method="max"); p
Out[3]: Poly(x^5 + 6x^4 + 6x^3 + 6x^2 + 6x + 6, GF(7))

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

# A random irreducible polynomial
In [5]: p = galois.irreducible_poly(7, 5, method="random"); p
Out[5]: Poly(x^5 + 4x^4 + 3x + 1, GF(7))

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

Products with non-zero constants are also irreducible.

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

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

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

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