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.

terms: int | str | None = None¶

The desired number of non-zero terms \(t\) in the polynomial.

• None (default): Disregards the number of terms while searching for the polynomial.

• int: The exact number of non-zero terms in the polynomial.

• "min": The minimum possible number of non-zero terms.

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

The search method for finding the irreducible polynomial.

• "min" (default): Returns the lexicographically first polynomial.

• "max": Returns the lexicographically last polynomial.

• "random": Returns a random polynomial.

Returns:¶

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

Raises:¶

RuntimeError – If no monic irreducible polynomial of degree \(m\) over \(\mathrm{GF}(q)\) with \(t\) terms exists. If terms is None or "min", this should never be raised.

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 first, lexicographically last, and a random monic irreducible polynomial.

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

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

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

Find the lexicographically first monic irreducible polynomial with four terms.

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

Find the lexicographically first monic irreducible polynomial with the minimum number of non-zero terms.

In [5]: galois.irreducible_poly(7, 3, terms="min")
Out[5]: Poly(x^3 + 2, GF(7))

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

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

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

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

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

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