galois.primitive_root

galois.primitive_root(n, start=1)

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\).

• start (int, optional) – Initial primitive root hypothesis. The resulting primitive root will be root >= start. The default is 1.

Returns

The first, smallest primitive root of unity modulo \(n\).

Return type

int

References

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

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

• https://www.ams.org/journals/mcom/1992-58-197/S0025-5718-1992-1106981-9/S0025-5718-1992-1106981-9.pdf

• https://www.ams.org/journals/bull/1942-48-10/S0002-9904-1942-07767-6/S0002-9904-1942-07767-6.pdf

• http://www.numbertheory.org/courses/MP313/lectures/lecture7/page1.html

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)

# The algorithm is also efficient for very large prime n
In [4]: galois.primitive_root(1000000000000000035000061)
Out[4]: 7