- classmethod galois.FieldArray.primitive_roots_of_unity(n: int) Self
Finds all primitive \(n\)-th roots of unity in the finite field.
- Parameters:¶
- 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\).
Notes¶
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 [1]: GF = galois.GF(31) In [2]: GF.primitive_roots_of_unity(2) Out[2]: GF([30], order=31) In [3]: GF.primitive_roots_of_unity(5) Out[3]: GF([ 2, 4, 8, 16], order=31) In [4]: GF.primitive_roots_of_unity(15) Out[4]: GF([ 7, 9, 10, 14, 18, 19, 20, 28], order=31)
However, they do not exist for \(n\) that do not divide 30.
In [5]: GF.primitive_roots_of_unity(7) --------------------------------------------------------------------------- ValueError Traceback (most recent call last) Cell In[5], line 1 ----> 1 GF.primitive_roots_of_unity(7) File ~/checkouts/readthedocs.org/user_builds/galois/envs/latest/lib/python3.8/site-packages/galois/_fields/_array.py:952, in FieldArray.primitive_roots_of_unity(cls, n) 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 [6]: root = GF.primitive_roots_of_unity(5); root Out[6]: GF([ 2, 4, 8, 16], order=31) In [7]: powers = np.arange(1, 5 + 1); powers Out[7]: array([1, 2, 3, 4, 5]) In [8]: np.power.outer(root, powers) Out[8]: GF([[ 2, 4, 8, 16, 1], [ 4, 16, 2, 8, 1], [ 8, 2, 16, 4, 1], [16, 8, 4, 2, 1]], order=31)