galois.primitive_elements¶

galois.primitive_elements(irreducible_poly, start=None, stop=None, reverse=False)¶

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

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

Parameters¶

irreducible_poly : Poly¶

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

start : Optional[int]¶

Starting value (inclusive, integer representation of the polynomial) in the search for primitive elements \(g(x)\) of \(\mathrm{GF}(p^m)\). The default is None which represents \(p\), which corresponds to \(g(x) = x\) over \(\mathrm{GF}(p)\).

stop : Optional[int]¶

Stopping value (exclusive, integer representation of the polynomial) in the search for primitive elements \(g(x)\) of \(\mathrm{GF}(p^m)\). The default is None which represents \(p^m\), which corresponds to \(g(x) = x^m\) over \(\mathrm{GF}(p)\).

reverse : bool¶

Search for primitive elements in reverse order, i.e. largest to smallest. Default is False.

Returns¶

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

Return type¶

List[Poly]

Examples

In [1]: GF = galois.GF(3)

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

In [3]: galois.is_irreducible(f)
Out[3]: True

In [4]: galois.is_primitive(f)
Out[4]: True

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

In [6]: len(g) == galois.euler_phi(3**2 - 1)
Out[6]: True

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

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

In [9]: galois.is_irreducible(f)
Out[9]: True

In [10]: galois.is_primitive(f)
Out[10]: False

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

In [12]: len(g) == galois.euler_phi(3**2 - 1)
Out[12]: True