galois.primitive_poly¶

galois.primitive_poly(order: int, degree: int, method: 'min' | 'max' | 'random' = 'min') → Poly¶

Returns a monic primitive 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 primitive polynomial.

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

The search method for finding the primitive polynomial.

• "min" (default): Returns the lexicographically-minimal monic primitive polynomial.

• "max": Returns the lexicographically-maximal monic primitive polynomial.

• "random": Returns a randomly generated degree-\(m\) monic primitive polynomial.

Returns

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

See also

Poly.is_primitive, matlab_primitive_poly, conway_poly

Notes

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

In addition to other applications, \(f(x)\) produces the field extension \(\mathrm{GF}(q^m)\) of \(\mathrm{GF}(q)\). Since \(f(x)\) is primitive, \(x\) is a primitive element \(\alpha\) of \(\mathrm{GF}(q^m)\) such that \(\mathrm{GF}(q^m) = \{0, 1, \alpha, \alpha^2, \dots, \alpha^{q^m-2}\}\).

Examples

Search methods

Find the lexicographically-minimal monic primitive polynomial.

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

Find the lexicographically-maximal monic primitive polynomial.

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

Find a random monic primitive polynomial.

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

Primitive vs. Conway

Notice primitive_poly() returns the lexicographically-minimal primitive polynomial but conway_poly() returns the lexicographically-minimal primitive polynomial that is consistent with smaller Conway polynomials.

This is sometimes the same polynomial.

In [4]: galois.primitive_poly(2, 4)
Out[4]: Poly(x^4 + x + 1, GF(2))

In [5]: galois.conway_poly(2, 4)
Out[5]: Poly(x^4 + x + 1, GF(2))

However, it is not always.

In [6]: galois.primitive_poly(7, 10)
Out[6]: Poly(x^10 + 5x^2 + x + 5, GF(7))

In [7]: galois.conway_poly(7, 10)
Out[7]: Poly(x^10 + x^6 + x^5 + 4x^4 + x^3 + 2x^2 + 3x + 3, GF(7))

Properties

Find a random monic primitive polynomial over \(\mathrm{GF}(7)\) with degree \(5\).

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

In [9]: f.is_primitive()
Out[9]: True

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

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

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

In [12]: g.is_primitive()
Out[12]: True