Determines whether an element of the extension field \(\mathrm{GF}(q^m)\) is normal.

Let \(f(x)\) be a degree-\(m\) irreducible polynomial over \(\mathrm{GF}(q)\) and let \(\alpha\) denote the residue class of \(x\) in the quotient

Every field element can be written uniquely as \(g(\alpha)\) with \(\deg g < m\). This function determines whether the element represented by the input polynomial \(g(x)\) is normal, i.e., whether its Frobenius conjugates \(\{g(\alpha), g(\alpha)^q, \dots, g(\alpha)^{q^{m-1}}\}\) form a basis of \(\mathrm{GF}(q^m)\) as a vector space over \(\mathrm{GF}(q)\).

Parameters:¶

element: PolyLike¶

A polynomial \(g(x)\) over \(\mathrm{GF}(q)\) with degree less than \(m\). This may be any PolyLike and will be converted to a Poly over the same field as irreducible_poly. The corresponding field element is the residue class \(g(\alpha)\) in \(\mathrm{GF}(q)[x] / (f(x))\), where \(\alpha\) is the image of \(x\) modulo \(f(x)\).

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:¶

True if the residue class \(g(\alpha)\) is a normal element of \(\mathrm{GF}(q^m)\) over \(\mathrm{GF}(q)\).

Notes¶

The field \(\mathrm{GF}(q^m)\) is an \(m\)-dimensional vector space over \(\mathrm{GF}(q)\). An element \(a \in \mathrm{GF}(q^m)\) is normal (over \(\mathrm{GF}(q)\)) if its Frobenius conjugates

form a basis of \(\mathrm{GF}(q^m)\) as a vector space over \(\mathrm{GF}(q)\).

Equivalently, an element \(a = g(\alpha)\) is normal if and only if its Frobenius conjugates are linearly independent over \(\mathrm{GF}(q)\), i.e., the only solution

is \(c_0 = \dots = c_{m-1} = 0\).

This function tests normality as follows.

1. Compute the Frobenius conjugates of \(a\):

   \[ a^{q^0}, a^{q^1}, \dots, a^{q^{m-1}}. \]

2. Express each conjugate as a polynomial over \(\mathrm{GF}(q)\) of degree less than \(m\):

   \[ a^{q^i} \leftrightarrow \sum_{j=0}^{m-1} c_{i,j} \alpha^j. \]

   The coefficient vector \((c_{i,0}, \dots, c_{i,m-1})\) is the coordinate vector of \(a^{q^i}\) in the power basis \(\{1, \alpha, \dots, \alpha^{m-1}\}\).

3. Form the \(m \times m\) matrix over \(\mathrm{GF}(q)\) whose columns are these coordinate vectors. The element is normal if and only if this matrix has full rank \(m\).

In this implementation, exponentiation in \(\mathrm{GF}(q^m)\) is performed via polynomial exponentiation modulo irreducible_poly using the built-in pow(), and coefficient vectors are obtained from the polynomial representatives of the Frobenius conjugates.

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

# x + 1 represents α + 1
In [2]: assert galois.is_normal_element("x + 1", f)

# x represents α
In [3]: assert not galois.is_normal_element("x", f)