- galois.primitive_elements(irreducible_poly: Poly) list[Poly]
Enumerates all primitive elements 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
\[ \mathrm{GF}(q^m) \cong \mathrm{GF}(q)[x] / (f(x)). \]This function returns all polynomials \(g(x)\) over \(\mathrm{GF}(q)\) with \(\deg g < m\) whose residue classes modulo \(f(x)\) are primitive generators of the multiplicative group \(\mathrm{GF}(q^m)^\times\).
- Parameters:¶
- Returns:¶
List of all polynomials \(g(x)\) over \(\mathrm{GF}(q)\) with degree less than \(m\) whose residue classes modulo \(f(x)\) are primitive elements of \(\mathrm{GF}(q^m)\).
Notes¶
The multiplicative group \(\mathrm{GF}(q^m)^\times\) is cyclic of order \(N = q^m - 1\). If \(g(\alpha)\) is any fixed primitive element, then all primitive elements of \(\mathrm{GF}(q^m)\) are precisely the powers
\[ g(\alpha)^k \quad \text{with} \quad \gcd(k, N) = 1. \]The number of primitive elements is \(\varphi(N)\), where \(\varphi\) is the Euler totient function. See
euler_phi.This function:
Finds one primitive representative polynomial \(g(x)\) using
primitive_element().Iterates over all integers \(k\) in the totatives of \(N\) (i.e., \(1 \le k < N\) and \(\gcd(k, N) = 1\)).
Computes \(g(x)^k \bmod f(x)\) in \(\mathrm{GF}(q)[x] / (f(x))\).
Returns the corresponding list of primitive representative polynomials.
Examples¶
Construct the extension field \(\mathrm{GF}(3^4)\).
In [1]: f = galois.irreducible_poly(3, 4, method="max"); f Out[1]: Poly(x^4 + 2x^3 + 2x^2 + x + 2, GF(3)) In [2]: GF = galois.GF(3**4, irreducible_poly=f, repr="poly") In [3]: print(GF.properties) Galois Field: name: GF(3^4) characteristic: 3 degree: 4 order: 81 irreducible_poly: x^4 + 2x^3 + 2x^2 + x + 2 is_primitive_poly: True primitive_element: xFind all primitive representative polynomials for the degree-4 extension of \(\mathrm{GF}(3)\).
In [4]: g = galois.primitive_elements(f); g Out[4]: [Poly(x, GF(3)), Poly(x + 1, GF(3)), Poly(2x, GF(3)), Poly(2x + 2, GF(3)), Poly(x^2 + 1, GF(3)), Poly(x^2 + 2x + 2, GF(3)), Poly(2x^2 + 2, GF(3)), Poly(2x^2 + x + 1, GF(3)), Poly(x^3, GF(3)), Poly(x^3 + 1, GF(3)), Poly(x^3 + x^2, GF(3)), Poly(x^3 + x^2 + 2, GF(3)), Poly(x^3 + x^2 + x, 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 + 2, 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 + 1, GF(3)), Poly(2x^3, GF(3)), Poly(2x^3 + 2, GF(3)), Poly(2x^3 + x^2, GF(3)), Poly(2x^3 + x^2 + 1, GF(3)), Poly(2x^3 + x^2 + x + 2, GF(3)), Poly(2x^3 + x^2 + 2x, GF(3)), Poly(2x^3 + x^2 + 2x + 2, GF(3)), Poly(2x^3 + 2x^2, GF(3)), Poly(2x^3 + 2x^2 + 1, GF(3)), Poly(2x^3 + 2x^2 + x, GF(3)), Poly(2x^3 + 2x^2 + x + 1, GF(3)), Poly(2x^3 + 2x^2 + 2x, GF(3))]The number of primitive elements is given by \(\varphi(q^m - 1)\).
In [5]: phi = galois.euler_phi(3**4 - 1); phi Out[5]: 32 In [6]: assert len(g) == phiShows that each representative polynomial corresponds to an element of multiplicative order \(q^m - 1\) in \(\mathrm{GF}(3^4)\).
# Convert the polynomials over GF(3) into elements of GF(3^4) In [7]: g = GF([int(gi) for gi in g]); g Out[7]: GF([ α, α + 1, 2α, 2α + 2, α^2 + 1, α^2 + 2α + 2, 2α^2 + 2, 2α^2 + α + 1, α^3, α^3 + 1, α^3 + α^2, α^3 + α^2 + 2, α^3 + α^2 + α, α^3 + α^2 + 2α, α^3 + α^2 + 2α + 2, α^3 + 2α^2, α^3 + 2α^2 + 2, α^3 + 2α^2 + α, α^3 + 2α^2 + α + 1, α^3 + 2α^2 + 2α + 1, 2α^3, 2α^3 + 2, 2α^3 + α^2, 2α^3 + α^2 + 1, 2α^3 + α^2 + α + 2, 2α^3 + α^2 + 2α, 2α^3 + α^2 + 2α + 2, 2α^3 + 2α^2, 2α^3 + 2α^2 + 1, 2α^3 + 2α^2 + α, 2α^3 + 2α^2 + α + 1, 2α^3 + 2α^2 + 2α], order=3^4) In [8]: assert np.all(g.multiplicative_order() == GF.order - 1)