galois.primitive_roots

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 [start, stop).

Parameters
n

A positive integer.

start

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

stop

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

reverse

Indicates 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

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

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 the 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 0x7fa26b2ab660>

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
Last update: May 18, 2022