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: 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.

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

• 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

Return full list

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

Use generator

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

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