galois.primitive_root

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

Finds the smallest primitive root 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 root, if found, will be \(\textrm{start} \le g < \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 root, if found, will be \(\textrm{start} \le g < \textrm{stop}\).

  • reverse (bool, optional) – 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

int

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

In [642]: root = galois.primitive_root(n); root
Out[642]: 5

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

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

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

# The primitive roots are the elements in Znx that multiplicatively generate the group
In [646]: 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

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

In [648]: root = galois.primitive_root(n); root
Out[648]: 3

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

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

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

# The primitive roots are the elements in Znx that multiplicatively generate the group
In [652]: 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

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

In [653]: n = 1000000000000000035000061

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

In [655]: galois.primitive_root(n, reverse=True)
Out[655]: 1000000000000000035000054

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 [656]: n = 8

In [657]: root = galois.primitive_root(n); root

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

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

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

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

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