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.

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 primitive polynomial.

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

• "max": Returns the lexicographically last polynomial.

• "random": Returns a random polynomial.

Returns:¶

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

Raises:¶

RuntimeError – If no monic primitive 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 a primitive polynomial over $\mathrm{GF}(q)$ and $a\in \mathrm{GF}(q)\mathrm{\setminus }\{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¶

Find the lexicographically first, lexicographically last, and a random monic primitive polynomial.

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

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

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

Find the lexicographically first monic primitive polynomial with four terms.

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

Notice primitive_poly() returns the lexicographically first primitive polynomial but conway_poly() returns the lexicographically first primitive polynomial that is consistent with smaller Conway polynomials. This is sometimes the same polynomial.

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

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

However, it is not always.

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

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

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

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

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

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

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

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