galois.FieldArray.primitive_root_of_unity

classmethod galois.FieldArray.primitive_root_of_unity(n: int) → Self

Finds a primitive $n$ -th root of unity in the finite field.

Parameters:¶

n: int¶: The root of unity.

Returns:¶

The primitive $n$ -th root of unity, a 0-D scalar array.

Raises:¶

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

Notes¶

A primitive $n$ -th root of unity $ω_{n}$ is such that $ω_{n}^{n} = 1$ and $ω_{n}^{k} \neq 1$ for all $1 \leq k < n$ .

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

Examples¶

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

In [1]: GF = galois.GF(31)

In [2]: GF.primitive_root_of_unity(2)
Out[2]: GF(30, order=31)

In [3]: GF.primitive_root_of_unity(5)
Out[3]: GF(16, order=31)

In [4]: GF.primitive_root_of_unity(15)
Out[4]: GF(9, order=31)

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

In [5]: GF.primitive_root_of_unity(7)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Cell In[5], line 1
----> 1 GF.primitive_root_of_unity(7)

File /opt/hostedtoolcache/Python/3.8.15/x64/lib/python3.8/site-packages/galois/_fields/_array.py:673, in FieldArray.primitive_root_of_unity(cls, n)
    671     raise ValueError(f"Argument 'n' must be in [1, {cls.order}), not {n}.")
    672 if not (cls.order - 1) % n == 0:
--> 673     raise ValueError(f"There are no primitive {n}-th roots of unity in {cls.name}.")
    675 return cls.primitive_element ** ((cls.order - 1) // n)

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

For $ω_{5}$ , one can see that $ω_{5}^{5} = 1$ and $ω_{5}^{k} \neq 1$ for $1 \leq k < 5$ .

In [6]: root = GF.primitive_root_of_unity(5); root
Out[6]: GF(16, order=31)

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

In [8]: root ** powers
Out[8]: GF([16,  8,  4,  2,  1], order=31)