galois.primitive_roots

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

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 to n. 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

list

References

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 [663]: n = 6

In [664]: roots = galois.primitive_roots(n); roots
Out[664]: [5]

# The congruence class coprime with n
In [665]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx
Out[665]: {1, 5}

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

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

# Test all elements for being primitive roots. The powers of a primitive span the congruence classes mod n.
In [668]: 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 [669]: len(roots) == galois.euler_totient(phi)
Out[669]: 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 [670]: n = 7

In [671]: roots = galois.primitive_roots(n); roots
Out[671]: [3, 5]

# The congruence class coprime with n
In [672]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx
Out[672]: {1, 2, 3, 4, 5, 6}

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

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

# Test all elements for being primitive roots. The powers of a primitive span the congruence classes mod n.
In [675]: 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 [676]: len(roots) == galois.euler_totient(phi)
Out[676]: True

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

In [677]: n = 1000000000000000035000061

# Euler's totient function phi(phi(n)) counts the primitive roots of n
In [678]: galois.euler_totient(galois.euler_totient(n))
Out[678]: 237770895725348415787008

# Only find some of the primitive roots
In [679]: galois.primitive_roots(n, stop=100)
Out[679]: [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 [680]: 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 [681]: n = 8

In [682]: roots = galois.primitive_roots(n); roots
Out[682]: []

# The congruence class coprime with n
In [683]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx
Out[683]: {1, 3, 5, 7}

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

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

# Test all elements for being primitive roots. The powers of a primitive span the congruence classes mod n.
In [686]: 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