- galois.is_cyclic(n: int) bool
Determines whether the multiplicative group \((\mathbb{Z}/n\mathbb{Z}){^\times}\) is cyclic.
- Parameters:¶
- Returns:¶
True
if the multiplicative group \((\mathbb{Z}/n\mathbb{Z}){^\times}\) is cyclic.
See also
Notes¶
The multiplicative group \((\mathbb{Z}/n\mathbb{Z}){^\times}\) is the set of positive integers \(1 \le a < n\) that are coprime with \(n\). \((\mathbb{Z}/n\mathbb{Z}){^\times}\) being cyclic means that some primitive root of \(n\), or generator, \(g\) can generate the group \(\{1, g, g^2, \dots, g^{\phi(n)-1}\}\), where \(\phi(n)\) is Euler’s totient function and calculates the order of the group. If \((\mathbb{Z}/n\mathbb{Z}){^\times}\) is cyclic, the number of primitive roots is found by \(\phi(\phi(n))\).
\((\mathbb{Z}/n\mathbb{Z}){^\times}\) is cyclic if and only if \(n\) is 2, 4, \(p^k\), or \(2p^k\), where \(p\) is an odd prime and \(k\) is a positive integer.
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).
For prime \(n\), a primitive root modulo \(n\) is also a primitive element of the Galois field \(\mathrm{GF}(n)\).
In [17]: n = 31 In [18]: galois.is_cyclic(n) Out[18]: True
A primitive element is a generator of the multiplicative group \(\mathrm{GF}(p)^{\times} = \{1, 2, \dots, p-1\} = \{1, g, g^2, \dots, g^{\phi(n)-1}\}\).
In [19]: GF = galois.GF(n) In [20]: galois.primitive_root(n) Out[20]: 3 In [21]: GF.primitive_element Out[21]: GF(3, order=31)
The number of primitive roots/elements is \(\phi(\phi(n))\).
In [22]: list(galois.primitive_roots(n)) Out[22]: [3, 11, 12, 13, 17, 21, 22, 24] In [23]: GF.primitive_elements Out[23]: GF([ 3, 11, 12, 13, 17, 21, 22, 24], order=31) In [24]: galois.euler_phi(galois.euler_phi(n)) Out[24]: 8