galois.primitive_elements

galois.primitive_elements(irreducible_poly: Poly) list[Poly]

Finds all primitive elements \(g\) of the Galois field \(\mathrm{GF}(q^m)\) with degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(q)\).

Parameters
irreducible_poly: Poly

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

Returns

List of all primitive elements of \(\mathrm{GF}(q^m)\) with irreducible polynomial \(f(x)\). Each primitive element \(g\) is a polynomial over \(\mathrm{GF}(q)\) with degree less than \(m\).

Notes

The number of primitive elements of \(\mathrm{GF}(q^m)\) is \(\phi(q^m - 1)\), where \(\phi(n)\) is the Euler totient function. See euler_phi.

Examples

Find all primitive elements for the degree \(4\) extension of \(\mathrm{GF}(3)\).

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

In [2]: g = galois.primitive_elements(f); g
Out[2]: 
[Poly(x, GF(3)),
 Poly(x + 2, GF(3)),
 Poly(2x, GF(3)),
 Poly(2x + 1, GF(3)),
 Poly(x^2 + x, GF(3)),
 Poly(x^2 + 2x + 2, GF(3)),
 Poly(2x^2 + x + 1, GF(3)),
 Poly(2x^2 + 2x, GF(3)),
 Poly(x^3, GF(3)),
 Poly(x^3 + 2, GF(3)),
 Poly(x^3 + x, GF(3)),
 Poly(x^3 + x + 2, GF(3)),
 Poly(x^3 + 2x + 2, GF(3)),
 Poly(x^3 + x^2 + 2x, GF(3)),
 Poly(x^3 + x^2 + 2x + 2, GF(3)),
 Poly(x^3 + 2x^2, GF(3)),
 Poly(x^3 + 2x^2 + 1, GF(3)),
 Poly(x^3 + 2x^2 + x, GF(3)),
 Poly(x^3 + 2x^2 + x + 1, GF(3)),
 Poly(x^3 + 2x^2 + 2x + 2, GF(3)),
 Poly(2x^3, GF(3)),
 Poly(2x^3 + 1, GF(3)),
 Poly(2x^3 + x + 1, GF(3)),
 Poly(2x^3 + 2x, GF(3)),
 Poly(2x^3 + 2x + 1, GF(3)),
 Poly(2x^3 + x^2, GF(3)),
 Poly(2x^3 + x^2 + 2, GF(3)),
 Poly(2x^3 + x^2 + x + 1, GF(3)),
 Poly(2x^3 + x^2 + 2x, GF(3)),
 Poly(2x^3 + x^2 + 2x + 2, GF(3)),
 Poly(2x^3 + 2x^2 + x, GF(3)),
 Poly(2x^3 + 2x^2 + x + 1, GF(3))]

Construct the extension field \(\mathrm{GF}(3^4)\). Note, by default, GF() uses a Conway polynomial as its irreducible polynomial.

In [3]: GF = galois.GF(3**4)

In [4]: print(GF.properties)
Galois Field:
  name: GF(3^4)
  characteristic: 3
  degree: 4
  order: 81
  irreducible_poly: x^4 + 2x^3 + 2
  is_primitive_poly: True
  primitive_element: x

In [5]: np.array_equal([int(gi) for gi in g], GF.primitive_elements)
Out[5]: True

The number of primitive elements is given by \(\phi(q^m - 1)\).

In [6]: phi = galois.euler_phi(3**4 - 1); phi
Out[6]: 32

In [7]: len(g) == phi
Out[7]: True

Last update: May 16, 2022