galois.normal_element(irreducible_poly: Poly, method: 'min' | 'max' | 'random' = 'min') → Poly

Finds a normal 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

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

This function searches for a polynomial \(g(x)\) over \(\mathrm{GF}(q)\) with \(\deg g < m\) whose residue class modulo \(f(x)\) is normal, i.e., whose Frobenius conjugates \(\{g(\alpha), g(\alpha)^q, \dots, g(\alpha)^{q^{m-1}}\}\) form a basis 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)). \]

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

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

  • "min": Return a normal representative with the smallest integer encoding.

  • "max": Return a normal representative with the largest integer encoding.

  • "random": Return a random normal 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 normal element of \(\mathrm{GF}(q^m)\) over \(\mathrm{GF}(q)\).

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 are never normal in \(\mathrm{GF}(q^m)\) for \(m > 1\), since their Frobenius conjugates do not span the \(m\)-dimensional extension space.

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\).

See also

is_normal_element, normal_elements

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 the smallest normal representative polynomial for \(\mathrm{GF}(2^3)\).

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

Find a random normal representative polynomial for \(\mathrm{GF}(2^3)\).

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