-
galois.irreducible_poly(order: int, degree: int, terms: int | str | None =
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: 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.
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.
For \(q = 2\), \(2 \le m \le 10000\),
terms="min"
, andmethod="min"
, the HP Table of Low-Weight Binary Irreducible Polynomials is used.
- 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
isNone
or"min"
, this should never be raised.
See also
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 + 2x^2 + 5x + 1, 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 + 6x^3 + 6x^2 + 4x + 3, GF(7)) In [8]: f.is_irreducible() Out[8]: True In [9]: g = f * GF(3); g Out[9]: Poly(3x^5 + 4x^3 + 4x^2 + 5x + 2, GF(7)) In [10]: g.is_irreducible() Out[10]: True