galois.primitive_root¶

galois.primitive_root(n, start=1, stop=None, reverse=False)¶

Finds the smallest primitive root modulo $n$.

Parameters¶

n : int¶

A positive integer.

start : int¶

Starting value (inclusive) in the search for a primitive root. The default is 1. The resulting primitive root, if found, will be $\text{start}\le g<\text{stop}$.

stop : Optional[int]¶

Stopping value (exclusive) in the search for a primitive root. The default is None which corresponds to $n$. The resulting primitive root, if found, will be $\text{start}\le g<\text{stop}$.

reverse : bool¶

Search for a primitive root in reverse order, i.e. find the largest primitive root first. Default is False.

Returns¶

The smallest primitive root modulo $n$. Returns None if no primitive roots exist.

Return type¶

Optional[int]

Notes

The integer $g$ is a primitive root modulo $n$ if the totatives of $n$, the positive integers $1\le a<n$ that are coprime with $n$, can be generated by powers of $g$.

Alternatively said, $g$ is a primitive root modulo $n$ if and only if $g$ is a generator of the multiplicative group of integers modulo $n$,

$$(\mathbb{Z}/n\mathbb{Z}){}^{\times }=\{1,g,g^2,\dots ,g^{\varphi (n)-1}\}$$

where $\varphi (n)$ is order of the group.

If $(\mathbb{Z}/n\mathbb{Z}){}^{\times }$ is cyclic, the number of primitive roots modulo $n$ is given by $\varphi (\varphi (n))$.

References

• 22. Shoup. Searching for primitive roots in finite fields. https://www.ams.org/journals/mcom/1992-58-197/S0025-5718-1992-1106981-9/S0025-5718-1992-1106981-9.pdf

• 12. 11. Hua. On the least primitive root of a prime. 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

The elements of $(\mathbb{Z}/n\mathbb{Z}){}^{\times }$ are the positive integers less than $n$ that are coprime with $n$. For example, $(\mathbb{Z}/14\mathbb{Z}){}^{\times }=\{1,3,5,9,11,13\}$.

# n is of type 2*p^k, which is cyclic
In [1]: n = 14

In [2]: galois.is_cyclic(n)
Out[2]: True

# The congruence class coprime with n
In [3]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx
Out[3]: {1, 3, 5, 9, 11, 13}

# Euler's totient function counts the "totatives", positive integers coprime with n
In [4]: phi = galois.euler_phi(n); phi
Out[4]: 6

In [5]: len(Znx) == phi
Out[5]: True

# The primitive roots are the elements in Znx that multiplicatively generate the group
In [6]: for a in Znx:
   ...:     span = set([pow(a, i, n) for i in range(1, phi + 1)])
   ...:     primitive_root = span == Znx
   ...:     print("Element: {:2d}, Span: {:<20}, Primitive root: {}".format(a, str(span), primitive_root))
   ...: 
Element:  1, Span: {1}                 , Primitive root: False
Element:  3, Span: {1, 3, 5, 9, 11, 13}, Primitive root: True
Element:  5, Span: {1, 3, 5, 9, 11, 13}, Primitive root: True
Element:  9, Span: {9, 11, 1}          , Primitive root: False
Element: 11, Span: {9, 11, 1}          , Primitive root: False
Element: 13, Span: {1, 13}             , Primitive root: False

# Find the smallest primitive root
In [7]: galois.primitive_root(n)
Out[7]: 3

# Find all primitive roots
In [8]: roots = galois.primitive_roots(n); roots
Out[8]: [3, 5]

# Euler's totient function ϕ(ϕ(n)) counts the primitive roots of n
In [9]: len(roots) == galois.euler_phi(phi)
Out[9]: True

A counterexample is $n=15=3\cdot 5$, which doesn’t fit the condition for cyclicness. $(\mathbb{Z}/15\mathbb{Z}){}^{\times }=\{1,2,4,7,8,11,13,14\}$.

# n is of type p1^k1 * p2^k2, which is not cyclic
In [10]: n = 15

In [11]: galois.is_cyclic(n)
Out[11]: False

# The congruence class coprime with n
In [12]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx
Out[12]: {1, 2, 4, 7, 8, 11, 13, 14}

# Euler's totient function counts the "totatives", positive integers coprime with n
In [13]: phi = galois.euler_phi(n); phi
Out[13]: 8

In [14]: len(Znx) == phi
Out[14]: True

# The primitive roots are the elements in Znx that multiplicatively generate the group
In [15]: for a in Znx:
   ....:     span = set([pow(a, i, n) for i in range(1, phi + 1)])
   ....:     primitive_root = span == Znx
   ....:     print("Element: {:2d}, Span: {:<13}, Primitive root: {}".format(a, str(span), primitive_root))
   ....: 
Element:  1, Span: {1}          , Primitive root: False
Element:  2, Span: {8, 1, 2, 4} , Primitive root: False
Element:  4, Span: {1, 4}       , Primitive root: False
Element:  7, Span: {1, 4, 13, 7}, Primitive root: False
Element:  8, Span: {8, 1, 2, 4} , Primitive root: False
Element: 11, Span: {1, 11}      , Primitive root: False
Element: 13, Span: {1, 4, 13, 7}, Primitive root: False
Element: 14, Span: {1, 14}      , Primitive root: False

# Find the smallest primitive root
In [16]: galois.primitive_root(n)

# Find all primitive roots
In [17]: roots = galois.primitive_roots(n); roots
Out[17]: []

# Note the max order of any element is 4, not 8, which is Carmichael's lambda function
In [18]: galois.carmichael_lambda(n)
Out[18]: 4

The algorithm is also efficient for very large $n$.

In [19]: n = 1000000000000000035000061

In [20]: galois.primitive_root(n)
Out[20]: 7