galois.primitive_root¶
-
galois.
primitive_root
(n)[source]¶ Finds the first, smallest primitive n-th root of unity \(x\) that satisfies \(x^n \equiv 1 (\textrm{mod}\ n)\).
- Parameters
n (int) – A positive integer \(n > 1\).
- Returns
The first, smallest primitive root of unity modulo \(n\).
- Return type
References
Examples
In [1]: n = 7 In [2]: root = galois.primitive_root(n); root Out[2]: 3 # Test that the primitive root is a multiplicative generator of GF(n) In [3]: for i in range(1, n): ...: result = galois.modular_exp(root, i, n) ...: print(f"{root}^{i} = {result} (mod {n})") ...: 3^1 = 3 (mod 7) 3^2 = 2 (mod 7) 3^3 = 6 (mod 7) 3^4 = 4 (mod 7) 3^5 = 5 (mod 7) 3^6 = 1 (mod 7)