# galois.primitive_root¶

galois.primitive_root(n: int, start: int = 1, stop: = None, method: Literal['min', 'max', 'random'] = 'min') int

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

Parameters
n

A positive integer.

start

Starting value (inclusive) in the search for a primitive root.

stop

Stopping value (exclusive) in the search for a primitive root. The default is None which corresponds to $$n$$.

method

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$$ $$(\mathbb{Z}/n\mathbb{Z}){^\times} = \{1, g, g^2, \dots, g^{\phi(n)-1}\}$$, where $$\phi(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 $$\phi(\phi(n))$$.

References

Examples

The elements of $$(\mathbb{Z}/14\mathbb{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 $$\phi(n)$$ function counts the totatives of $$n$$, which is equivalent to the order of $$(\mathbb{Z}/n\mathbb{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 $$2p^k$$, the multiplicative group $$(\mathbb{Z}/14\mathbb{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 $$(\mathbb{Z}/14\mathbb{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 $$(\mathbb{Z}/14\mathbb{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]


A non-cyclic group is $$(\mathbb{Z}/15\mathbb{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 $$2p^k$$, the multiplicative group $$(\mathbb{Z}/15\mathbb{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 $$\lambda(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)
File ~/checkouts/readthedocs.org/user_builds/galois/checkouts/v0.0.30/galois/_modular.py:576, in primitive_root(n, start, stop, method)
575 if method == "min":
--> 576     return next(primitive_roots(n, start, stop=stop))
577 elif method == "max":

StopIteration:

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

RuntimeError                              Traceback (most recent call last)
Input In [16], in <cell line: 1>()
----> 1 galois.primitive_root(n)

File ~/checkouts/readthedocs.org/user_builds/galois/checkouts/v0.0.30/galois/_modular.py:582, in primitive_root(n, start, stop, method)
580         return _primitive_root_random_search(n, start, stop)
581 except StopIteration as e:
--> 582     raise RuntimeError(f"No primitive roots modulo {n} exist in the range [{start}, {stop}).") from e

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


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]: 499312820205684368196011


Last update: Jul 12, 2022