galois.irreducible_poly(order: int, degree: int, terms: = None, method: 'min' | 'max' | 'random' = 'min') Poly

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: = 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.

Faster performance

Depending on the type of polynomial requested, this function may use a database of precomputed polynomials. Under these conditions, this function returns very quickly.

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.

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 : galois.irreducible_poly(7, 3)
Out: Poly(x^3 + 2, GF(7))

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

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


Find the lexicographically-first monic irreducible polynomial with four terms.

In : galois.irreducible_poly(7, 3, terms=4)
Out: 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 : galois.irreducible_poly(7, 3, terms="min")
Out: Poly(x^3 + 2, GF(7))


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

In : GF = galois.GF(7)

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

In : f.is_irreducible()
Out: True

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

In : g.is_irreducible()
Out: True