galois

A performant numpy extension for Galois fields.

Classes

GF2(array[, dtype])

Galois field array class for \(\mathrm{GF}(2)\) fields.

GF2m(*args, **kwargs)

An abstract base class for all \(\mathrm{GF}(2^m)\) field array classes.

GFp(*args, **kwargs)

An abstract base class for all \(\mathrm{GF}(p)\) field array classes.

Poly(coeffs[, field, order])

A polynomial class with coefficients in any Galois field.

Class Factory Functions

GF_factory(characteristic, degree[, …])

Factory function to construct Galois field array classes of type \(\mathrm{GF}(p^m)\).

Functions

carmichael(n)

Finds the smallest positive integer \(m\) such that \(a^m \equiv 1 (\textrm{mod}\ n)\) for every integer \(a\) in \(1 \le a < n\) that is coprime to \(n\).

chinese_remainder_theorem(a, m)

Solves the simultaneous system of congruences for \(x\).

conway_poly(characteristic, degree)

Returns the Conway polynomial for \(\mathrm{GF}(p^m)\).

euclidean_algorithm(a, b)

Finds the greatest common divisor of two integers.

euler_totient(n)

Counts the positive integers (totatives) in \(1 \le k < n\) that are relatively prime to \(n\), i.e. \(gcd(n, k) = 1\).

extended_euclidean_algorithm(a, b)

Finds the integer multiplicands of \(a\) and \(b\) such that \(a x + b y = gcd(a,b)\).

factors(x)

Computes the positive factors of the integer \(x\).

is_prime(x)

Determines if \(x\) is prime.

next_prime(x)

Returns the nearest prime \(p > x\).

prev_prime(x)

Returns the nearest prime \(p \le x\).

prime_factors(x)

Computes the prime factors of the positive integer \(x\).

primitive_root(n)

Finds the first, smallest primitive n-th root of unity \(x\) that satisfies \(x^n \equiv 1 (\textrm{mod}\ n)\).

primitive_roots(n)

Finds all primitive n-th roots of unity \(x\) that satisfy \(x^n \equiv 1 (\textrm{mod}\ n)\).
class galois.GF2(array, dtype=<class 'numpy.int64'>)[source]

Bases: galois.gf.GFBase, galois.gf.GFArray

Galois field array class for \(\mathrm{GF}(2)\) fields.

Parameters

  • array (array_like) – The input array to be converted to a Galois field array. The input array is copied, so the original array is unmodified by changes to the Galois field array. Valid input array types are numpy.ndarray, list, tuple, or int.

  • dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is numpy.int64.

Returns

The copied input array as a \(\mathrm{GF}(2)\) field array.

Return type

galois.GF2

Examples

GF2 class properties

In [1]: print(galois.GF2)
<Galois Field: GF(2^1), prim_poly = x + 1 (3 decimal)>

In [2]: galois.GF2.characteristic
Out[2]: 2

In [3]: galois.GF2.degree
Out[3]: 1

In [4]: galois.GF2.order
Out[4]: 2

In [5]: galois.GF2.prim_poly
Out[5]: Poly(x + 1, GF2)

Construct arrays in GF2

In [6]: a = galois.GF2([1,0,1,1]); a
Out[6]: GF2([1, 0, 1, 1])

In [7]: b = galois.GF2([1,1,1,1]); b
Out[7]: GF2([1, 1, 1, 1])

Arithmetic with GF2 arrays

# Element-wise addition
In [1]: a + b
Out[1]: GF2([0, 1, 0, 0])

# Element-wise subtraction
In [2]: a - b
Out[2]: GF2([0, 1, 0, 0])

# Element-wise multiplication
In [3]: a * b
Out[3]: GF2([1, 0, 1, 1])

# Element-wise division
In [4]: a / b
Out[4]: GF2([1, 0, 1, 1])
classmethod target(target)[source]

Retarget the just-in-time compiled numba ufuncs.

Parameters

target (str) – The target keyword argument from numba.vectorize, either "cpu", "parallel", or "cuda".

alpha = GF2(1)

The primitive element of the Galois field \(\mathrm{GF}(p^m)\). The primitive element is a root of the primitive polynomial \(p(x)\), such that \(p(\alpha) = 0\). The primitive element is also a multiplicative generator of the field, such that \(\mathrm{GF}(p^m) = \{0, 1, \alpha^1, \alpha^2, \dots, \alpha^{p^m - 2}\}\).

Type

int

characteristic = 2

The prime characteristic \(p\) of the Galois field \(\mathrm{GF}(p^m)\). Adding \(p\) copies of any element will always result in \(0\).

Type

int

degree = 1

The prime characteristic’s degree \(m\) of the Galois field \(\mathrm{GF}(p^m)\). The degree is a positive integer.

Type

int

dtypes = [<class 'numpy.uint8'>, <class 'numpy.uint16'>, <class 'numpy.uint32'>, <class 'numpy.int8'>, <class 'numpy.int16'>, <class 'numpy.int32'>, <class 'numpy.int64'>]

List of valid integer numpy.dtype objects that are compatible with this Galois field array class. Valid data types are signed and unsinged integers that can represent decimal values in \([0, p^m)\).

Type

list

order = 2

The order \(p^m\) of the Galois field \(\mathrm{GF}(p^m)\). The order of the field is also equal to the field’s size.

Type

int

prim_poly = Poly(x + 1, GF2)

The primitive polynomial \(p(x)\) of the Galois field \(\mathrm{GF}(p^m)\). The primitive polynomial is of degree \(m\) in \(\mathrm{GF}(p)[x]\).

Type

galois.Poly

ufunc_mode = 'calculate'

The mode for ufunc compilation, either "lookup" or "calculate".

Type

str

ufunc_target = 'cpu'

The numba target for the JIT-compiled ufuncs, either "cpu", "parallel", or "cuda".

Type

str

class galois.GF2m(*args, **kwargs)[source]

Bases: galois.gf.GFBase, galois.gf.GFArray

An abstract base class for all \(\mathrm{GF}(2^m)\) field array classes.

Parameters

  • array (array_like) – The input array to be converted to a Galois field array. The input array is copied, so the original array is unmodified by changes to the Galois field array. Valid input array types are numpy.ndarray, list, tuple, or int.

  • dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is numpy.int64.

Returns

The copied input array as a \(\mathrm{GF}(2^m)\) field array.

Return type

galois.GF2m

Note

This is an abstract base class for all \(\mathrm{GF}(2^m)\) fields. It cannot be instantiated directly. \(\mathrm{GF}(2^m)\) field classes are created using galois.GF_factory.

classmethod target(target, mode, rebuild=False)[source]

Retarget the just-in-time compiled numba ufuncs.

Parameters

  • target (str) – The target keyword argument from numba.vectorize, either "cpu", "parallel", or "cuda".

  • mode (str) – The type of field computation, either "lookup" or "calculate". The “lookup” mode will use Zech log, log, and anti-log lookup tables for speed. The “calculate” mode will not store any lookup tables, but perform field arithmetic on the fly. The “calculate” mode is designed for large fields that cannot store lookup tables in RAM. Generally, “calculate” will be slower than “lookup”.

  • rebuild (bool, optional) – Indicates whether to force a rebuild of the lookup tables. The default is False.

class galois.GFp(*args, **kwargs)[source]

Bases: galois.gf.GFBase, galois.gf.GFArray

An abstract base class for all \(\mathrm{GF}(p)\) field array classes.

Parameters

  • array (array_like) – The input array to be converted to a Galois field array. The input array is copied, so the original array is unmodified by changes to the Galois field array. Valid input array types are numpy.ndarray, list, tuple, or int.

  • dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is numpy.int64.

Returns

The copied input array as a \(\mathrm{GF}(p)\) field array.

Return type

galois.GFp

Note

This is an abstract base class for all \(\mathrm{GF}(p)\) fields. It cannot be instantiated directly. \(\mathrm{GF}(p)\) field classes are created using galois.GF_factory.

classmethod target(target, mode, rebuild=False)[source]

Retarget the just-in-time compiled numba ufuncs.

Parameters

  • target (str) – The target keyword argument from numba.vectorize, either "cpu", "parallel", or "cuda".

  • mode (str) – The type of field computation, either "lookup" or "calculate". The “lookup” mode will use Zech log, log, and anti-log lookup tables for speed. The “calculate” mode will not store any lookup tables, but perform field arithmetic on the fly. The “calculate” mode is designed for large fields that cannot store lookup tables in RAM. Generally, “calculate” will be slower than “lookup”.

  • rebuild (bool, optional) – Indicates whether to force a rebuild of the lookup tables. The default is False.

class galois.Poly(coeffs, field=None, order='desc')[source]

Bases: object

A polynomial class with coefficients in any Galois field.

Parameters

  • coeffs (array_like) – List of polynomial coefficients of type Galois field array, np.ndarray, list, or tuple. The first element is the highest-degree element if order="desc" or the first element is the 0-th degree element if order="asc".

  • field (galois.GFBase, optional) – Optionally specify the field to which the coefficients belong. The default field is galois.GF2. If coeffs is a Galois field array, then that field is used and the field parameter is ignored.

  • order (str, optional) – The interpretation of the coefficient degrees, either "desc" (default) or "asc". For "desc", the first element of coeffs is the highest degree coefficient (x^(N-1)) and the last element is the 0-th degree element (x^0).

Examples

Create polynomials over GF(2)

# Construct a polynominal over GF(2)
In [1]: a = galois.Poly([1,0,1,1]); a
Out[1]: Poly(x^3 + x + 1, GF2)

# Construct the same polynomial by only specifying its non-zero coefficients
In [2]: b = galois.Poly.NonZero([1,1,1], [3,1,0]); b
Out[2]: Poly(x^3 + x + 1, GF2)

Create polynomials over GF(7)

# Construct the GF(7) field
In [3]: GF = galois.GF_factory(7, 1)

# Construct a polynominal over GF(7)
In [4]: galois.Poly([4,0,3,0,0,2], field=GF)
Out[4]: Poly(4x^5 + 3x^3 + 2, GF7)

# Construct the same polynomial by only specifying its non-zero coefficients
In [5]: galois.Poly.NonZero([4,3,2], [5,3,0], field=GF)
Out[5]: Poly(4x^5 + 3x^3 + 2, GF7)

Polynomial arithmetic

In [1]: a = galois.Poly([1,0,6,3], field=GF); a
Out[1]: Poly(x^3 + 6x + 3, GF7)

In [2]: b = galois.Poly([2,0,2], field=GF); b
Out[2]: Poly(2x^2 + 2, GF7)

In [3]: a + b
Out[3]: Poly(x^3 + 2x^2 + 6x + 5, GF7)

In [4]: a - b
Out[4]: Poly(x^3 + 5x^2 + 6x + 1, GF7)

# Compute the quotient of the polynomial division
In [5]: a / b
Out[5]: Poly(4x, GF7)

# True division and floor division are equivalent
In [6]: a / b == a // b
Out[6]: True

# Compute the remainder of the polynomial division
In [7]: a % b
Out[7]: Poly(5x + 3, GF7)
classmethod Decimal(decimal, field=<class 'galois.gf2.GF2'>, order='desc')[source]
classmethod NonZero(coeffs, degrees, field=<class 'galois.gf2.GF2'>)[source]

Examples

# Construct a polynomial over GF2 only specifying the non-zero terms
In [1]: a = galois.Poly.NonZero([1,1,1], [3,1,0]); a
Out[1]: Poly(x^3 + x + 1, GF2)
static divmod(dividend, divisor)[source]
property coeffs

The polynomial coefficients as a Galois field array. Coefficients are \([a_{N-1}, \dots, a_1, a_0]\) if order="desc" or \([a_0, a_1, \dots, a_{N-1}]\) if order="asc", where \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\).

Type

galois.GF2, galois.GF2m, galois.GFp, galois.GFpm

property coeffs_asc

The polynomial coefficients \([a_0, a_1, \dots, a_{N-1}]\) as a Galois field array in exponent-ascending order, where \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\).

Type

galois.GF2, galois.GF2m, galois.GFp, galois.GFpm

property coeffs_desc

The polynomial coefficients \([a_{N-1}, \dots, a_1, a_0]\) as a Galois field array in exponent-ascending order, where \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\).

Type

galois.GF2, galois.GF2m, galois.GFp, galois.GFpm

property decimal

The integer representation of the polynomial. For \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\) with elements in \(\mathrm{GF}(q)\), the decimal representation is \(d = a_{N-1} q^{N-1} + \dots + a_1 q + a_0\) (using integer arithmetic, not field arithmetic) where \(q\) is the field order.

Type

int

property degree

The degree of the polynomial, i.e. the highest degree with non-zero coefficient.

Type

int

property field

The finite field to which the coefficients belong.

Type

galois.GF2, galois.GF2m, galois.GFp, galois.GFpm

property order

The interpretation of the ordering of the polynomial coefficients. coeffs are in exponent-descending order if order="desc" and in exponent-ascending order if order="asc".

Type

str

property str

The string representation of the polynomial.

Type

str

galois.GF_factory(characteristic, degree, prim_poly=None, target='cpu', mode='auto', rebuild=False)[source]

Factory function to construct Galois field array classes of type \(\mathrm{GF}(p^m)\).

Parameters

  • characteristic (int) – The prime characteristic \(p\) of the field \(\mathrm{GF}(p^m)\).

  • degree (int) – The prime characteristic’s degree \(m\) of the field \(\mathrm{GF}(p^m)\).

  • prim_poly (galois.Poly, optional) – The primitive polynomial of the field. Default is None which will use the Conway polynomial obtained from galois.conway_poly.

  • target (str) – The target keyword argument from numba.vectorize, either "cpu", "parallel", or "cuda".

  • mode (str, optional) – The type of field computation, either "auto", "lookup", or "calculate". The default is "auto". The “lookup” mode will use Zech log, log, and anti-log lookup tables for speed. The “calculate” mode will not store any lookup tables, but perform field arithmetic on the fly. The “calculate” mode is designed for large fields that cannot store lookup tables in RAM. Generally, “calculate” will be slower than “lookup”. The “auto” mode will determine whether to use “lookup” or “calculate” based on the field size. For “auto”, field’s with order <= 2**16 will use the “lookup” mode.

  • rebuild (bool, optional) – Indicates whether to force a rebuild of the lookup tables. The default is False.

Returns

A new Galois field class that is a sublcass of galois.GFBase.

Return type

galois.GF2, galois.GF2m, galois.GFp, galois.GFpm

galois.carmichael(n)[source]

Finds the smallest positive integer \(m\) such that \(a^m \equiv 1 (\textrm{mod}\ n)\) for every integer \(a\) in \(1 \le a < n\) that is coprime to \(n\).

Implements the Carmichael function \(\lambda(n)\).

Parameters

n (int) – A positive integer.

Returns

The smallest positive integer \(m\) such that \(a^m \equiv 1 (\textrm{mod}\ n)\) for every \(a\) in \(1 \le a < n\) that is coprime to \(n\).

Return type

int

References

Examples

In [1]: n = 20

In [2]: lambda_ = galois.carmichael(n); lambda_
Out[2]: 4

# Find the totatives that are relatively coprime with n
In [3]: totatives = [i for i in range(n) if galois.euclidean_algorithm(i, n) == 1]; totatives
Out[3]: [1, 3, 7, 9, 11, 13, 17, 19]

In [4]: for a in totatives:
   ...:     result = galois.modular_exp(a, lambda_, n)
   ...:     print("{:2d}^{} = {} (mod {})".format(a, lambda_, result, n))
   ...: 
 1^4 = 1 (mod 20)
 3^4 = 1 (mod 20)
 7^4 = 1 (mod 20)
 9^4 = 1 (mod 20)
11^4 = 1 (mod 20)
13^4 = 1 (mod 20)
17^4 = 1 (mod 20)
19^4 = 1 (mod 20)

# For prime n, phi and lambda are always n-1
In [5]: galois.euler_totient(13), galois.carmichael(13)
Out[5]: (12, 12)
galois.chinese_remainder_theorem(a, m)[source]

Solves the simultaneous system of congruences for \(x\).

\[ \begin{align}\begin{aligned}x &\equiv a_1\ (\textrm{mod}\ m_1)\\x &\equiv a_2\ (\textrm{mod}\ m_2)\\x &\equiv \ldots\\x &\equiv a_n\ (\textrm{mod}\ m_n)\end{aligned}\end{align} \]
Parameters

  • a (array_like) – The integer remainders \(a_i\).

  • m (array_like) – The integer modulii \(m_i\).

Returns

The simultaneous solution \(x\) to the system of congruences.

Return type

int

Examples

In [1]: a = [0, 3, 4]

In [2]: m = [3, 4, 5]

In [3]: x = galois.chinese_remainder_theorem(a, m); x
Out[3]: 39

In [4]: for i in range(len(a)):
   ...:     ai = x % m[i]
   ...:     print(f"{x} % {m[i]} = {ai}, Valid congruence: {ai == a[i]}")
   ...: 
39 % 3 = 0, Valid congruence: True
39 % 4 = 3, Valid congruence: True
39 % 5 = 4, Valid congruence: True
galois.conway_poly(characteristic, degree)[source]

Returns the Conway polynomial for \(\mathrm{GF}(p^m)\).

This function uses Frank Luebeck’s Conway polynomial database. See: http://www.math.rwth-aachen.de/~Frank.Luebeck/data/ConwayPol/index.html.

Parameters

  • characteristic (int) – The prime characteristic \(p\) of the field \(\mathrm{GF}(p^m)\).

  • degree (int) – The prime characteristic’s degree \(m\) of the field \(\mathrm{GF}(p^m)\).

Returns

The degree-\(m\) polynomial in \(\mathrm{GF}(p)[x]\).

Return type

galois.Poly

Note

If the \(\mathrm{GF}(p)\) field hasn’t already been created, it will be created in this function since it’s needed in the return polynomial.

Examples

In [1]: galois.conway_poly(2, 100)
Out[1]: Poly(x^100 + x^57 + x^56 + x^55 + x^52 + x^48 + x^47 + x^46 + x^45 + x^44 + x^43 + x^41 + x^37 + x^36 + x^35 + x^34 + x^31 + x^30 + x^27 + x^25 + x^24 + x^22 + x^20 + x^19 + x^16 + x^15 + x^11 + x^9 + x^8 + x^6 + x^5 + x^3 + 1, GF2)

In [2]: galois.conway_poly(7, 13)
Out[2]: Poly(x^13 + 6x^2 + 4, GF7)
galois.euclidean_algorithm(a, b)[source]

Finds the greatest common divisor of two integers.

Parameters

  • a (int) – Any integer.

  • b (int) – Any integer.

Returns

Greatest common divisor of \(a\) and \(b\), i.e. \(gcd(a,b)\).

Return type

int

References

Examples

In [1]: a, b = 2, 13

In [2]: galois.euclidean_algorithm(a, b)
Out[2]: 1
galois.euler_totient(n)[source]

Counts the positive integers (totatives) in \(1 \le k < n\) that are relatively prime to \(n\), i.e. \(gcd(n, k) = 1\).

Implements the Euler Totient function \(\phi(n)\).

Parameters

n (int) – A positive integer.

Returns

The number of totatives that are relatively prime to \(n\).

Return type

int

References

Examples

In [1]: n = 20

In [2]: phi = galois.euler_totient(n); phi
Out[2]: 8

# Find the totatives that are relatively coprime with n
In [3]: totatives = [i for i in range(n) if galois.euclidean_algorithm(i, n) == 1]; totatives
Out[3]: [1, 3, 7, 9, 11, 13, 17, 19]

# The number of totatives is phi
In [4]: len(totatives) == phi
Out[4]: True

# For prime n, phi is always n-1
In [5]: galois.euler_totient(13)
Out[5]: 12
galois.extended_euclidean_algorithm(a, b)[source]

Finds the integer multiplicands of \(a\) and \(b\) such that \(a x + b y = gcd(a,b)\).

Parameters

  • a (int) – Any integer.

  • b (int) – Any integer.

Returns

  • int – Integer \(x\), such that \(a x + b y = gcd(a, b)\).

  • int – Integer \(y\), such that \(a x + b y = gcd(a, b)\).

  • int – Greatest common divisor of \(a\) and \(b\).

References

Examples

In [1]: a, b = 2, 13

In [2]: x, y, gcd = galois.extended_euclidean_algorithm(a, b)

In [3]: x, y, gcd
Out[3]: (-6, 1, 1)

In [4]: a*x + b*y == gcd
Out[4]: True
galois.factors(x)[source]

Computes the positive factors of the integer \(x\).

Parameters

x (int) – An integer to be factored.

Returns

Sorted array of factors of \(x\).

Return type

numpy.ndarray

Examples

In [1]: galois.factors(120)
Out[1]: 
array([  1,   2,   3,   4,   5,   6,   8,  10,  12,  15,  20,  24,  30,
        40,  60, 120])
galois.is_prime(x)[source]

Determines if \(x\) is prime.

Parameters

x (int) – A positive integer.

Returns

True if the integer \(x\) is prime.

Return type

bool

Examples

In [1]: galois.is_prime(13)
Out[1]: True

In [2]: galois.is_prime(15)
Out[2]: False
galois.next_prime(x)[source]

Returns the nearest prime \(p > x\).

Parameters

x (int) – A positive integer.

Returns

The nearest prime \(p > x\).

Return type

int

Examples

In [1]: galois.next_prime(13)
Out[1]: 17

In [2]: galois.next_prime(15)
Out[2]: 17
galois.prev_prime(x)[source]

Returns the nearest prime \(p \le x\).

Parameters

x (int) – A positive integer.

Returns

The nearest prime \(p \le x\).

Return type

int

Examples

In [1]: galois.prev_prime(13)
Out[1]: 13

In [2]: galois.prev_prime(15)
Out[2]: 13
galois.prime_factors(x)[source]

Computes the prime factors of the positive integer \(x\).

The integer \(x\) can be factored into \(x = p_1^{k_1} p_2^{k_2} \dots p_{n-1}^{k_{n-1}}\).

Parameters

x (int) – The positive integer to be factored.

Returns

  • numpy.ndarray – Sorted array of prime factors \(p = [p_1, p_2, \dots, p_{n-1}]\) with \(p_1 < p_2 < \dots < p_{n-1}\).

  • numpy.ndarray – Array of corresponding prime powers \(k = [k_1, k_2, \dots, k_{n-1}]\).

Examples

In [1]: p, k = galois.prime_factors(120)

In [2]: p, k
Out[2]: (array([2, 3, 5]), array([3, 1, 1]))

# The product of the prime powers is the factored integer
In [3]: np.multiply.reduce(p ** k)
Out[3]: 120
galois.primitive_root(n)[source]

Finds the first, smallest primitive n-th root of unity \(x\) that satisfies \(x^n \equiv 1 (\textrm{mod}\ n)\).

Parameters

n (int) – A positive integer \(n > 1\).

Returns

The first, smallest primitive root of unity modulo \(n\).

Return type

int

References

Examples

In [1]: n = 7

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

# Test that the primitive root is a multiplicative generator of GF(n)
In [3]: for i in range(1, n):
   ...:     result = galois.modular_exp(root, i, n)
   ...:     print(f"{root}^{i} = {result} (mod {n})")
   ...: 
3^1 = 3 (mod 7)
3^2 = 2 (mod 7)
3^3 = 6 (mod 7)
3^4 = 4 (mod 7)
3^5 = 5 (mod 7)
3^6 = 1 (mod 7)
galois.primitive_roots(n)[source]

Finds all primitive n-th roots of unity \(x\) that satisfy \(x^n \equiv 1 (\textrm{mod}\ n)\).

Parameters

n (int) – A positive integer \(n > 1\).

Returns

A list of integer roots of unity modulo \(n\).

Return type

list

References

Examples

In [1]: n = 7

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

# Test that each primitive root is a multiplicative generator of GF(n)
In [3]: for root in roots:
   ...:     print(f"\nPrimitive root: {root}")
   ...:     for i in range(1, n):
   ...:         result = galois.modular_exp(root, i, n)
   ...:         print(f"{root}^{i} = {result} (mod {n})")
   ...: 

Primitive root: 3
3^1 = 3 (mod 7)
3^2 = 2 (mod 7)
3^3 = 6 (mod 7)
3^4 = 4 (mod 7)
3^5 = 5 (mod 7)
3^6 = 1 (mod 7)

Primitive root: 5
5^1 = 5 (mod 7)
5^2 = 4 (mod 7)
5^3 = 6 (mod 7)
5^4 = 2 (mod 7)
5^5 = 3 (mod 7)
5^6 = 1 (mod 7)