classmethod galois.FieldArray.primitive_roots_of_unity(n: int) Self

Finds all primitive $$n$$-th roots of unity in the finite field.

Parameters:
n: int

The root of unity.

Returns:

All primitive $$n$$-th roots of unity, a 1-D array. The roots are sorted in lexicographical order.

Raises:

ValueError – If no primitive $$n$$-th roots of unity exist. This happens when $$n$$ is not a divisor of $$p^m - 1$$.

A primitive $$n$$-th root of unity $$\omega_n$$ is such that $$\omega_n^n = 1$$ and $$\omega_n^k \ne 1$$ for all $$1 \le k \lt n$$.

In $$\mathrm{GF}(p^m)$$, a primitive $$n$$-th root of unity exists when $$n$$ divides $$p^m - 1$$. Then, the primitive root is $$\omega_n = \alpha^{(p^m - 1)/n}$$ where $$\alpha$$ is a primitive element of the field.

Examples

In $$\mathrm{GF}(31)$$, primitive roots exist for all divisors of 30.

In : GF = galois.GF(31)

In : GF.primitive_roots_of_unity(2)
Out: GF(, order=31)

In : GF.primitive_roots_of_unity(5)
Out: GF([ 2,  4,  8, 16], order=31)

In : GF.primitive_roots_of_unity(15)
Out: GF([ 7,  9, 10, 14, 18, 19, 20, 28], order=31)


However, they do not exist for $$n$$ that do not divide 30.

In : GF.primitive_roots_of_unity(7)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Cell In, line 1
----> 1 GF.primitive_roots_of_unity(7)

950     raise TypeError(f"Argument 'n' must be an int, not {type(n)!r}.")
951 if not (cls.order - 1) % n == 0:
--> 952     raise ValueError(f"There are no primitive {n}-th roots of unity in {cls.name}.")
954 roots = np.unique(cls.primitive_elements ** ((cls.order - 1) // n))
955 roots = np.sort(roots)

ValueError: There are no primitive 7-th roots of unity in GF(31).


For $$\omega_5$$, one can see that $$\omega_5^5 = 1$$ and $$\omega_5^k \ne 1$$ for $$1 \le k \lt 5$$.

In : root = GF.primitive_roots_of_unity(5); root
Out: GF([ 2,  4,  8, 16], order=31)

In : powers = np.arange(1, 5 + 1); powers
Out: array([1, 2, 3, 4, 5])

In : np.power.outer(root, powers)
Out:
GF([[ 2,  4,  8, 16,  1],
[ 4, 16,  2,  8,  1],
[ 8,  2, 16,  4,  1],
[16,  8,  4,  2,  1]], order=31)