Finds a primitive element of the extension field \(\mathrm{GF}(q^m)\) defined by an irreducible polynomial.

Let \(f(x)\) be a degree-\(m\) irreducible polynomial over \(\mathrm{GF}(q)\) and let

This function searches for a polynomial \(g(x)\) over \(\mathrm{GF}(q)\) with \(\deg g < m\) whose residue class modulo \(f(x)\) is primitive, i.e., generates the multiplicative group \(\mathrm{GF}(q^m)^\times\) of order \(q^m - 1\).

Parameters:¶

irreducible_poly: Poly¶

The degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(q)\) that defines the extension field

\[ \mathrm{GF}(q^m) \cong \mathrm{GF}(q)[x] / (f(x)). \]

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

The search method for finding a primitive representative polynomial. Choices are:

• "min": Returns a primitive representative with the smallest integer encoding.

• "max": Returns a primitive representative with the largest integer encoding.

• "random": Returns a random primitive representative.

Returns:¶

A polynomial \(g(x)\) over \(\mathrm{GF}(q)\) with degree less than \(m\) such that its residue class modulo \(f(x)\) is a primitive element of \(\mathrm{GF}(q^m)\).

Notes¶

Integers in the range \([0, q^m - 1]\) correspond to polynomials over \(\mathrm{GF}(q)\) with degree less than \(m\) via the usual base-\(q\) expansion. Each such polynomial \(g(x)\) represents a unique residue class \(g(\alpha)\) in \(\mathrm{GF}(q)[x] / (f(x))\).

Constant polynomials (integers \(0, 1, \dots, q - 1\)) represent elements of the base field \(\mathrm{GF}(q)\) and can never be primitive in \(\mathrm{GF}(q^m)\) for \(m > 1\), since their multiplicative orders divide \(q - 1\).

Therefore, this function searches over integers in the range \([q, q^m - 1]\), which correspond to non-constant polynomials \(g(x)\) of degree at most \(m - 1\).

Examples¶

Construct the extension field \(\mathrm{GF}(7^5)\).

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

In [2]: GF = galois.GF(7**5, irreducible_poly=f, repr="poly")

In [3]: print(GF.properties)
Galois Field:
  name: GF(7^5)
  characteristic: 7
  degree: 5
  order: 16807
  irreducible_poly: x^5 + 6x^4 + 6x^3 + 6x^2 + 6x + 6
  is_primitive_poly: False
  primitive_element: x + 3

Find the smallest primitive representative polynomial for the degree-5 extension of \(\mathrm{GF}(7)\) with irreducible polynomial \(f(x)\).

In [4]: g = galois.primitive_element(f); g
Out[4]: Poly(x + 3, GF(7))

# Convert the polynomial over GF(7) into an element of GF(7^5)
In [5]: g = GF(int(g)); g
Out[5]: GF(x + 3, order=7^5)

In [6]: assert g.multiplicative_order() == GF.order - 1

Find the largest primitive representative polynomial for the degree-5 extension of \(\mathrm{GF}(7)\) with irreducible polynomial \(f(x)\).

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

# Convert the polynomial over GF(7) into an element of GF(7^5)
In [8]: g = GF(int(g)); g
Out[8]: GF(6x^4 + 6x^3 + 6x^2 + 6x + 3, order=7^5)

In [9]: assert g.multiplicative_order() == GF.order - 1

Find a random primitive representative polynomial for the degree-5 extension of \(\mathrm{GF}(7)\) with irreducible polynomial \(f(x)\).

In [10]: g = galois.primitive_element(f, method="random"); g
Out[10]: Poly(3x^4 + 3x^3 + 3x^2 + x + 1, GF(7))

# Convert the polynomial over GF(7) into an element of GF(7^5)
In [11]: g = GF(int(g)); g
Out[11]: GF(3x^4 + 3x^3 + 3x^2 + x + 1, order=7^5)

In [12]: assert g.multiplicative_order() == GF.order - 1