-
galois.primitive_root(n: int, start: int =
1
, stop: int | None =None
, method: 'min' | 'max' | 'random' ='min'
) int Finds a primitive root 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.
- stop: int | None =
None
¶ Stopping value (exclusive) in the search for a primitive root. The default is
None
which corresponds to \(n\).- method: 'min' | 'max' | 'random' =
'min'
¶ 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.
See also
primitive_roots
,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 the 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¶
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 /opt/hostedtoolcache/Python/3.11.10/x64/lib/python3.11/site-packages/galois/_modular.py:560, in primitive_root(n, start, stop, method) 559 if method == "min": --> 560 root = next(primitive_roots(n, start, stop=stop)) 561 elif method == "max": StopIteration: The above exception was the direct cause of the following exception: RuntimeError Traceback (most recent call last) Cell In[16], line 1 ----> 1 galois.primitive_root(n) File /opt/hostedtoolcache/Python/3.11.10/x64/lib/python3.11/site-packages/galois/_modular.py:567, in primitive_root(n, start, stop, method) 565 return root 566 except StopIteration as e: --> 567 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]: 157294399397961409563377