galois.normal_elements(irreducible_poly: Poly) → list[Poly]

Enumerates all normal 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 normal elements of \(\mathrm{GF}(q^m)\) 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) \cong \mathrm{GF}(q)[x] / (f(x)). \]

Returns:

List of all polynomials \(g(x)\) over \(\mathrm{GF}(q)\) with degree less than \(m\) whose residue classes modulo \(f(x)\) are normal elements of \(\mathrm{GF}(q^m)\) over \(\mathrm{GF}(q)\).

Notes

The number of normal elements depends only on \((q, m)\) and not on the particular choice of irreducible polynomial \(f(x)\) used to construct the field.

A convenient theoretical description is via the polynomial Euler totient over \(\mathrm{GF}(q)\). If

\[ x^m - 1 = \prod_i P_i(x)^{e_i} \]

is the factorization of \(x^m - 1\) into monic irreducible polynomials over \(\mathrm{GF}(q)\), then the number of normal elements of \(\mathrm{GF}(q^m)\) over \(\mathrm{GF}(q)\) is

\[ N(q, m) = q^m \prod_i \left(1 - \frac{1}{q^{\deg P_i}}\right) \]

when \(x^m - 1\) is squarefree (the general case can be expressed in terms of a polynomial totient function \(\varphi_q\); see standard references on normal bases). In particular, \(N(q, m)\) is independent of the irreducible polynomial \(f(x)\) that defines the field.

This function does not use the above product formula internally; instead, it enumerates normal elements explicitly:

  1. Iterate over integers \(n\) in the range \([q, q^m - 1]\), which correspond to non-constant polynomials of degree less than \(m\) via the base-\(q\) encoding.

  2. Convert each integer to a polynomial \(g(x)\) using Poly.Int().

  3. Test whether the residue class of \(g(x)\) is normal using is_normal_element().

  4. Collect all such \(g(x)\).

For large fields, this enumeration is expensive (\(O(q^m)\) normality tests). For many applications, it is preferable to use normal_element() to obtain a single normal element efficiently via a (typically fast) randomized search.

See also

is_normal_element, normal_element

Examples

Construct the extension field \(\mathrm{GF}(2^3)\) with irreducible polynomial \(f(x) = x^3 + x + 1\).

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

Find all normal representative polynomials for \(\mathrm{GF}(2^3)\).

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

In [3]: assert len(g) == 3