galois.primitive_roots

galois.primitive_roots(n)

Finds all primitive n-th roots of unity \(x\) that satisfy \(x^n \equiv 1 (\textrm{mod}\ n)\).

Parameters

n (int) – A positive integer \(n > 1\).

Returns

A list of integer roots of unity modulo \(n\).

Return type

list

References

• https://en.wikipedia.org/wiki/Finite_field#Roots_of_unity

• https://en.wikipedia.org/wiki/Primitive_root_modulo_n

Examples

In [1]: n = 7

In [2]: roots = galois.primitive_roots(n); roots
Out[2]: [3, 5]

# Test that each primitive root is a multiplicative generator of GF(n)
In [3]: for root in roots:
   ...:     print(f"\nPrimitive root: {root}")
   ...:     for i in range(1, n):
   ...:         result = galois.modular_exp(root, i, n)
   ...:         print(f"{root}^{i} = {result} (mod {n})")
   ...: 

Primitive root: 3
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)

Primitive root: 5
5^1 = 5 (mod 7)
5^2 = 4 (mod 7)
5^3 = 6 (mod 7)
5^4 = 2 (mod 7)
5^5 = 3 (mod 7)
5^6 = 1 (mod 7)