galois.primitive_roots(n: int, start: int = 1, stop: int | None = None, reverse: bool = False) → Iterator[int]

Iterates through all primitive roots modulo \(n\) in the range \([\texttt{start}, \texttt{stop})\).

Parameters:
n: int

A positive integer.

start: int = 1

Starting value (inclusive) in the search for primitive roots. The default is 1.

stop: int | None = None

Stopping value (exclusive) in the search for primitive roots. The default is None, which corresponds to n.

reverse: bool = False

Indicates whether to return the primitive roots from largest to smallest. The default is False.

Returns:

An iterator over the primitive roots modulo \(n\) in the specified range.

See also

primitive_root, is_primitive_root, is_cyclic, totatives, euler_phi, carmichael_lambda

Notes

An integer \(g\) is a primitive root modulo \(n\) if and only if it generates the multiplicative group of units \((\mathbb{Z}/n\mathbb{Z})^\times\):

\[ (\mathbb{Z}/n\mathbb{Z})^\times = \{ [g^0]_n, [g^1]_n, \dots, [g^{\varphi(n)-1}]_n \}. \]

If \((\mathbb{Z}/n\mathbb{Z})^\times\) is cyclic, the number of primitive roots modulo \(n\) is \(\varphi(\varphi(n))\), and this function yields all such roots (within the specified range) in increasing order by default, or decreasing order when reverse=True.

If \((\mathbb{Z}/n\mathbb{Z})^\times\) is not cyclic (see is_cyclic()), then no primitive roots exist and this generator yields no values.

For efficiency, when \(n\) is even and the group is cyclic, the search automatically skips even candidates since they cannot be units modulo \(n\).

The special cases n = 1 and n = 2 are handled by convention:

  • For n = 1, the generator yields a single value 0.

  • For n = 2, the generator yields a single value 1.

References

Examples

All primitive roots modulo 31. You may also use tuple() on the returned generator.

In [1]: list(galois.primitive_roots(31))
Out[1]: [3, 11, 12, 13, 17, 21, 22, 24]

There are no primitive roots modulo 30.

In [2]: list(galois.primitive_roots(30))
Out[2]: []

Show that each primitive root modulo 22 generates the multiplicative group \((\mathbb{Z}/22\mathbb{Z})^\times\).

In [3]: n = 22

In [4]: Znx = galois.totatives(n); Znx
Out[4]: [1, 3, 5, 7, 9, 13, 15, 17, 19, 21]

In [5]: phi = galois.euler_phi(n); phi
Out[5]: 10

In [6]: for root in galois.primitive_roots(22):
   ...:     span = set(pow(root, i, n) for i in range(0, phi))
   ...:     print(f"Element: {root:>2}, Span: {span}")
   ...: 
Element:  7, Span: {1, 3, 5, 7, 9, 13, 15, 17, 19, 21}
Element: 13, Span: {1, 3, 5, 7, 9, 13, 15, 17, 19, 21}
Element: 17, Span: {1, 3, 5, 7, 9, 13, 15, 17, 19, 21}
Element: 19, Span: {1, 3, 5, 7, 9, 13, 15, 17, 19, 21}

Find the three largest primitive roots modulo 31 in reversed order.

In [7]: generator = galois.primitive_roots(31, reverse=True); generator
Out[7]: <generator object primitive_roots at 0x7f134041e0e0>

In [8]: [next(generator) for _ in range(3)]
Out[8]: [24, 22, 21]

Loop over all the primitive roots in reversed order, only finding them as needed. The search cost for the roots that would have been found after the break condition is never incurred.

In [9]: for root in galois.primitive_roots(31, reverse=True):
   ...:     print(root)
   ...:     if root % 7 == 0:  # Arbitrary early exit condition
   ...:         break
   ...: 
24
22
21