galois.primitive_roots¶
-
galois.
primitive_roots
(n, start=1, stop=None, reverse=False)[source]¶ Finds all primitive roots modulo \(n\).
\(g\) is a primitive root if the totatives of \(n\), the positive integers \(1 \le a < n\) that are coprime with \(n\), can be generated by powers of \(g\).
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^\times}\). That is, \(\mathbb{Z}{_n^\times} = \{g, g^2, \dots, g^k\}\), where \(k\) is order of the group. The order of the group \(\mathbb{Z}{_n^\times}\) is defined by Euler’s totient function, \(\phi(n) = k\). If \(\mathbb{Z}{_n^\times}\) is cyclic, the number of primitive roots modulo \(n\) is given by \(\phi(k)\) or \(\phi(\phi(n))\).
See
galois.is_cyclic
.- Parameters
n (int) – A positive integer.
start (int, optional) – Starting value (inclusive) in the search for a primitive root. The default is 1. The resulting primitive roots, if found, will be \(\textrm{start} \le x < \textrm{stop}\).
stop (int, optional) – Stopping value (exclusive) in the search for a primitive root. The default is
None
which corresponds ton
. The resulting primitive roots, if found, will be \(\textrm{start} \le x < \textrm{stop}\).reverse (bool, optional) – List all primitive roots in descending order, i.e. largest to smallest. Default is
False
.
- Returns
All the positive primitive \(n\)-th roots of unity, \(x\).
- Return type
References
Shoup. 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
http://www.numbertheory.org/courses/MP313/lectures/lecture7/page1.html
Examples
Here is an example with one primitive root, \(n = 6 = 2 * 3^1\), which fits the definition of cyclicness, see
galois.is_cyclic
. Because \(n = 6\) is not prime, the primitive root isn’t a multiplicative generator of \(\mathbb{Z}/\textbf{n}\mathbb{Z}\).In [1]: n = 6 In [2]: roots = galois.primitive_roots(n); roots Out[2]: [5] # The congruence class coprime with n In [3]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx Out[3]: {1, 5} # Euler's totient function counts the "totatives", positive integers coprime with n In [4]: phi = galois.euler_totient(n); phi Out[4]: 2 In [5]: len(Znx) == phi Out[5]: True # Test all elements for being primitive roots. The powers of a primitive span the congruence classes mod n. In [6]: for a in Znx: ...: span = set([pow(a, i, n) for i in range(1, phi + 1)]) ...: primitive_root = span == Znx ...: print("Element: {}, Span: {:<6}, Primitive root: {}".format(a, str(span), primitive_root)) ...: Element: 1, Span: {1} , Primitive root: False Element: 5, Span: {1, 5}, Primitive root: True # Euler's totient function phi(phi(n)) counts the primitive roots of n In [7]: len(roots) == galois.euler_totient(phi) Out[7]: True
Here is an example with two primitive roots, \(n = 7 = 7^1\), which fits the definition of cyclicness, see
galois.is_cyclic
. Since \(n = 7\) is prime, the primitive root is a multiplicative generator of \(\mathbb{Z}/\textbf{n}\mathbb{Z}\).In [8]: n = 7 In [9]: roots = galois.primitive_roots(n); roots Out[9]: [3, 5] # The congruence class coprime with n In [10]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx Out[10]: {1, 2, 3, 4, 5, 6} # Euler's totient function counts the "totatives", positive integers coprime with n In [11]: phi = galois.euler_totient(n); phi Out[11]: 6 In [12]: len(Znx) == phi Out[12]: True # Test all elements for being primitive roots. The powers of a primitive span the congruence classes mod n. In [13]: for a in Znx: ....: span = set([pow(a, i, n) for i in range(1, phi + 1)]) ....: primitive_root = span == Znx ....: print("Element: {}, Span: {:<18}, Primitive root: {}".format(a, str(span), primitive_root)) ....: Element: 1, Span: {1} , Primitive root: False Element: 2, Span: {1, 2, 4} , Primitive root: False Element: 3, Span: {1, 2, 3, 4, 5, 6}, Primitive root: True Element: 4, Span: {1, 2, 4} , Primitive root: False Element: 5, Span: {1, 2, 3, 4, 5, 6}, Primitive root: True Element: 6, Span: {1, 6} , Primitive root: False # Euler's totient function phi(phi(n)) counts the primitive roots of n In [14]: len(roots) == galois.euler_totient(phi) Out[14]: True
The algorithm is also efficient for very large \(n\).
In [15]: n = 1000000000000000035000061 # Euler's totient function phi(phi(n)) counts the primitive roots of n In [16]: galois.euler_totient(galois.euler_totient(n)) Out[16]: 237770897832817345778688 # Only find some of the primitive roots In [17]: galois.primitive_roots(n, stop=100) Out[17]: [7, 21, 28, 34, 35, 38, 39, 43, 47, 52, 58, 65, 67, 73, 88, 97, 98] # The generator can also be used in a for loop In [18]: for r in galois.primitive_roots(n, stop=100): ....: print(r, end=" ") ....: 7 21 28 34 35 38 39 43 47 52 58 65 67 73 88 97 98
Here is a counterexample with no primitive roots, \(n = 8 = 2^3\), which does not fit the definition of cyclicness, see
galois.is_cyclic
.In [19]: n = 8 In [20]: roots = galois.primitive_roots(n); roots Out[20]: [] # The congruence class coprime with n In [21]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx Out[21]: {1, 3, 5, 7} # Euler's totient function counts the "totatives", positive integers coprime with n In [22]: phi = galois.euler_totient(n); phi Out[22]: 4 In [23]: len(Znx) == phi Out[23]: True # Test all elements for being primitive roots. The powers of a primitive span the congruence classes mod n. In [24]: for a in Znx: ....: span = set([pow(a, i, n) for i in range(1, phi + 1)]) ....: primitive_root = span == Znx ....: print("Element: {}, Span: {:<6}, Primitive root: {}".format(a, str(span), primitive_root)) ....: Element: 1, Span: {1} , Primitive root: False Element: 3, Span: {1, 3}, Primitive root: False Element: 5, Span: {1, 5}, Primitive root: False Element: 7, Span: {1, 7}, Primitive root: False