galois.primitive_root

galois.primitive_root(n: int, start: int = 1, stop: int | None = None, method: 'min' | 'max' | 'random' = 'min') → int

Finds a primitive root modulo $n$ in the range $[start, stop)$ .

Parameters¶

n: int¶: A positive integer.
start: int = 1¶: Starting value (inclusive) in the search for a primitive root.
stop: int | None = None¶: Stopping value (exclusive) in the search for a primitive root. The default is None which corresponds to $n$ .
method: 'min' | 'max' | 'random' = 'min'¶: The search method for finding the primitive root.

Returns¶

A primitive root modulo $n$ in the specified range.

Raises¶

RuntimeError – If no primitive roots exist in the specified range.

Notes¶

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

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$ $(Z / n Z)^{\times} = {1, g, g^{2}, \dots, g^{ϕ (n) - 1}}$ , where $ϕ (n)$ is order of the group.

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

References¶

Shoup, V. 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
Hua, L.K. 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¶

n = 14

The elements of $(Z / 14 Z)^{\times} = {1, 3, 5, 9, 11, 13}$ are the totatives of 14.

In [1]: n = 14

In [2]: Znx = galois.totatives(n); Znx
Out[2]: [1, 3, 5, 9, 11, 13]

The Euler totient $ϕ (n)$ function counts the totatives of $n$ , which is equivalent to the order of $(Z / n Z)^{\times}$ .

In [3]: phi = galois.euler_phi(n); phi
Out[3]: 6

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

Since 14 is of the form $2 p^{k}$ , the multiplicative group $(Z / 14 Z)^{\times}$ is cyclic, meaning there exists at least one element that generates the group by its powers.

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

Find the smallest primitive root modulo 14. Observe that the powers of $g$ uniquely represent each element in $(Z / 14 Z)^{\times}$ .

In [6]: g = galois.primitive_root(n); g
Out[6]: 3

In [7]: [pow(g, i, n) for i in range(0, phi)]
Out[7]: [1, 3, 9, 13, 11, 5]

Find the largest primitive root modulo 14. Observe that the powers of $g$ also uniquely represent each element in $(Z / 14 Z)^{\times}$ , although in a different order.

In [8]: g = galois.primitive_root(n, method="max"); g
Out[8]: 5

In [9]: [pow(g, i, n) for i in range(0, phi)]
Out[9]: [1, 5, 11, 13, 9, 3]

n = 15

A non-cyclic group is $(Z / 15 Z)^{\times} = {1, 2, 4, 7, 8, 11, 13, 14}$ .

In [10]: n = 15

In [11]: Znx = galois.totatives(n); Znx
Out[11]: [1, 2, 4, 7, 8, 11, 13, 14]

In [12]: phi = galois.euler_phi(n); phi
Out[12]: 8

Since 15 is not of the form 2, 4, $p^{k}$ , or $2 p^{k}$ , the multiplicative group $(Z / 15 Z)^{\times}$ is not cyclic, meaning no elements exist whose powers generate the group.

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

Below, every element is tested to see if it spans the group.

In [14]: for a in Znx:
   ....:     span = set([pow(a, i, n) for i in range(0, phi)])
   ....:     primitive_root = span == set(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

The Carmichael $λ (n)$ function finds the maximum multiplicative order of any element, which is 4 and not 8.

In [15]: galois.carmichael_lambda(n)
Out[15]: 4

Observe that no primitive roots modulo 15 exist and a RuntimeError is raised.

In [16]: galois.primitive_root(n)
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
~/repos/galois/galois/_modular.py in primitive_root(n, start, stop, method)
    578         if method == "min":
--> 579             return next(primitive_roots(n, start, stop=stop))
    580         elif method == "max":

StopIteration: 

The above exception was the direct cause of the following exception:

RuntimeError                              Traceback (most recent call last)
<ipython-input-16-bb1af462e9d6> in <module>
----> 1 galois.primitive_root(n)

~/repos/galois/galois/_modular.py in primitive_root(n, start, stop, method)
    583             return _primitive_root_random_search(n, start, stop)
    584     except StopIteration as e:
--> 585         raise RuntimeError(f"No primitive roots modulo {n} exist in the range [{start}, {stop}).") from e
    586 
    587 

RuntimeError: No primitive roots modulo 15 exist in the range [1, 15).

Very large n

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

In [17]: n = 1000000000000000035000061

In [18]: phi = galois.euler_phi(n); phi
Out[18]: 1000000000000000035000060

Find the smallest, the largest, and a random primitive root modulo $n$ .

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

In [20]: galois.primitive_root(n, method="max")
Out[20]: 1000000000000000035000054

In [21]: galois.primitive_root(n, method="random")
Out[21]: 782711146103537637262812