galois.primitive_root

galois.primitive_root(n, start=1, stop=None, reverse=False)

Finds the smallest primitive root modulo \(n\).

Parameters
n : int

A positive integer.

start : int

Starting value (inclusive) in the search for a primitive root. The default is 1. The resulting primitive root, if found, will be \(\textrm{start} \le g < \textrm{stop}\).

stop : Optional[int]

Stopping value (exclusive) in the search for a primitive root. The default is None which corresponds to \(n\). The resulting primitive root, if found, will be \(\textrm{start} \le g < \textrm{stop}\).

reverse : bool

Search for a primitive root in reverse order, i.e. find the largest primitive root first. Default is False.

Returns

The smallest primitive root modulo \(n\). Returns None if no primitive roots exist.

Return type

Optional[int]

Notes

The integer \(g\) is a primitive root modulo \(n\) 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\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

Examples

The elements of \((\mathbb{Z}/n\mathbb{Z}){^\times}\) are the positive integers less than \(n\) that are coprime with \(n\). For example, \((\mathbb{Z}/14\mathbb{Z}){^\times} = \{1, 3, 5, 9, 11, 13\}\).

# n is of type 2*p^k, which is cyclic
In [1]: n = 14

In [2]: galois.is_cyclic(n)
Out[2]: True

# 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, 3, 5, 9, 11, 13}

# Euler's totient function counts the "totatives", positive integers coprime with n
In [4]: phi = galois.euler_phi(n); phi
Out[4]: 6

In [5]: len(Znx) == phi
Out[5]: True

# The primitive roots are the elements in Znx that multiplicatively generate the group
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: {:2d}, Span: {:<20}, Primitive root: {}".format(a, str(span), primitive_root))
   ...: 
Element:  1, Span: {1}                 , Primitive root: False
Element:  3, Span: {1, 3, 5, 9, 11, 13}, Primitive root: True
Element:  5, Span: {1, 3, 5, 9, 11, 13}, Primitive root: True
Element:  9, Span: {9, 11, 1}          , Primitive root: False
Element: 11, Span: {9, 11, 1}          , Primitive root: False
Element: 13, Span: {1, 13}             , Primitive root: False

# Find the smallest primitive root
In [7]: galois.primitive_root(n)
Out[7]: 3

# Find all primitive roots
In [8]: roots = galois.primitive_roots(n); roots
Out[8]: [3, 5]

# Euler's totient function ϕ(ϕ(n)) counts the primitive roots of n
In [9]: len(roots) == galois.euler_phi(phi)
Out[9]: True

A counterexample is \(n = 15 = 3 \cdot 5\), which doesn’t fit the condition for cyclicness. \((\mathbb{Z}/15\mathbb{Z}){^\times} = \{1, 2, 4, 7, 8, 11, 13, 14\}\).

# n is of type p1^k1 * p2^k2, which is not cyclic
In [10]: n = 15

In [11]: galois.is_cyclic(n)
Out[11]: False

# The congruence class coprime with n
In [12]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx
Out[12]: {1, 2, 4, 7, 8, 11, 13, 14}

# Euler's totient function counts the "totatives", positive integers coprime with n
In [13]: phi = galois.euler_phi(n); phi
Out[13]: 8

In [14]: len(Znx) == phi
Out[14]: True

# The primitive roots are the elements in Znx that multiplicatively generate the group
In [15]: for a in Znx:
   ....:     span = set([pow(a, i, n) for i in range(1, phi + 1)])
   ....:     primitive_root = span == 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

# Find the smallest primitive root
In [16]: galois.primitive_root(n)

# Find all primitive roots
In [17]: roots = galois.primitive_roots(n); roots
Out[17]: []

# Note the max order of any element is 4, not 8, which is Carmichael's lambda function
In [18]: galois.carmichael_lambda(n)
Out[18]: 4

The algorithm is also efficient for very large \(n\).

In [19]: n = 1000000000000000035000061

In [20]: galois.primitive_root(n)
Out[20]: 7

Last update: Apr 03, 2022