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

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 ring

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)\) has multiplicative order \(q^m - 1\), i.e., generates \(\mathrm{GF}(q^m)^\times\).

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 primitive element of \(\mathrm{GF}(q^m)\), otherwise False.

Notes¶

An element \(g(\alpha)\) is primitive if it generates the entire multiplicative group, i.e., its multiplicative order is exactly \(N\).

This function implements the standard group-theoretic test for primitivity, using the representative polynomial \(g(x)\) modulo \(f(x)\).

1. Factor \(N\) into primes

   \[ N = \prod_i p_i^{e_i}, \]

   and let \(\{p_i\}\) be the set of distinct prime factors.

2. For each prime factor \(p_i\) of \(N\), compute

   \[ h_i = g(\alpha)^{N / p_i}. \]

   If \(h_i = 1\) for any \(i\), then the order of \(g(\alpha)\) is a proper divisor of \(N\), so \(g(\alpha)\) is not primitive.

3. If none of these powers equals \(1\), and \(g(\alpha)^N = 1\), then the multiplicative order of \(g(\alpha)\) is exactly \(N\) and the element is primitive.

In this implementation, element is the polynomial \(g(x)\), irreducible_poly is \(f(x)\), and exponentiation is performed in the quotient ring \(\mathrm{GF}(q)[x] / (f(x))\) via the built-in pow() with the modulus irreducible_poly.

The expression pow(element, k, irreducible_poly) computes the residue class of \(g(x)^k\) modulo \(f(x)\), which corresponds to \(g(\alpha)^k\) in \(\mathrm{GF}(q^m)\).

Examples¶

In the extension field \(\mathrm{GF}(3^4)\), the polynomial \(g(x) = x + 2\) represents a primitive element whose order is \(3^4 - 1 = 80\).

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

In [2]: f = GF.irreducible_poly; f
Out[2]: Poly(x^4 + 2x^3 + 2, GF(3))

In [3]: assert galois.is_primitive_element("x + 2", f)

In [4]: GF("x + 2").multiplicative_order()
Out[4]: 80

However, the polynomial \(x + 1\) does not represent a primitive element, as its multiplicative order is only 20.

In [5]: assert not galois.is_primitive_element("x + 1", f)

In [6]: GF("x + 1").multiplicative_order()
Out[6]: 20