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

Parameters¶

n: int¶

A positive integer.

start: int = 1¶

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

stop: int | None = None¶

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

reverse: bool = False¶

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.

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¶

• 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¶

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 0x7f9269df7580>

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