galois.irreducible_poly¶

galois.irreducible_poly(characteristic, degree, method='random')¶

Returns a degree-\(m\) irreducible polynomial \(f(x)\) over \(\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 polynomial that produces the field extension \(\mathrm{GF}(p^m)\) of \(\mathrm{GF}(p)\).
method (str, optional) – The search method for finding the irreducible polynomial, either "random" (default), "smallest", or "largest". The random search method will randomly generate degree-\(m\) polynomials and test for irreducibility. The smallest/largest search method will produce polynomials in increasing/decreasing lexicographical order and test for irreducibility.

Returns

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

Return type

galois.Poly

Examples

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

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

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

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

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

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

For the extension field \(\mathrm{GF}(2^8)\), notice the lexicographically-smallest irreducible polynomial is not primitive. The Conway polynomial \(C_{2,8}\) is the lexicographically-smallest irreducible and primitive polynomial.

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

In [8]: galois.is_irreducible(p), galois.is_primitive(p)
Out[8]: (True, False)

In [9]: p = galois.conway_poly(2, 8); p
Out[9]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))

In [10]: galois.is_irreducible(p), galois.is_primitive(p)
Out[10]: (True, True)