galois

A performant numpy extension for Galois fields.

Class Factory Functions

GF(order[, prim_poly, target, mode, rebuild])

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

Classes

GF2(array[, dtype, copy, order, ndmin])

Create an array over \(\mathrm{GF}(2)\).

GFArray(array[, dtype, copy, order, ndmin])

Create an array over \(\mathrm{GF}(p^m)\).

Poly(coeffs[, field, order])

Create a polynomial \(p(x)\) over \(\mathrm{GF}(q)\).

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(p, n)

Returns the degree-\(n\) Conway polynomial \(C_{p,n}\) over \(\mathrm{GF}(p)\).

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\).

factors(n)

Returns the positive factors of the integer \(n\).

fermat_primality_test(n)

Probabilistic primality test of \(n\).

gcd(a, b)

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

is_cyclic(n)

Determines whether the multiplicative group \(\mathbb{Z}{_n^\times}\) is cyclic.

is_irreducible(poly)

Checks whether the polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is irreducible.

is_prime(n)

Determines if \(n\) is prime.

is_primitive_root(g, n)

Determines if \(g\) is a primitive root modulo \(n\).

isqrt(n)

Computes the integer square root of \(n\) such that \(\textrm{isqrt}(n)^2 \le n\).

kth_prime(k)

Returns the \(k\)-th prime.

mersenne_exponents([n])

Returns all known Mersenne exponents \(e\) for \(e \le n\).

mersenne_primes([n])

Returns all known Mersenne primes \(p\) for \(p \le 2^n - 1\).

miller_rabin_primality_test(n[, a, rounds])

Probabilistic primality test of \(n\).

next_prime(x)

Returns the nearest prime \(p\), such that \(p > x\).

poly_exp_mod(poly, power, modulus)

Efficiently exponentiates a polynomial \(f(x)\) to the power \(k\) reducing by modulo \(g(x)\), \(f^k\ \textrm{mod}\ g\).

poly_gcd(a, b)

Finds the greatest common divisor of two polynomials \(a(x)\) and \(b(x)\) over \(\mathrm{GF}(q)\).

prev_prime(x)

Returns the nearest prime \(p\), such that \(p \le x\).

prime_factors(x)

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

primes(n)

Returns the primes \(p \le n\).

primitive_root(n[, start, stop, largest])

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

primitive_roots(n[, start, stop, reverse])

A generator that finds all primitive roots modulo \(n\).

totatives(n)

Returns the positive integers (totatives) in \(1 \le k < n\) that are relatively prime to \(n\), i.e. \(gcd(n, k) = 1\).
class galois.GF2(array, dtype=None, copy=True, order='K', ndmin=0)[source]

Bases: galois.gf.GFArray

Create an array over \(\mathrm{GF}(2)\).

Note

This Galois field class is a pre-made subclass of galois.GFArray. It is included in the package because of the ubiquity of \(\mathrm{GF}(2)\) fields.

# The pre-made GF(2) class
In [1]: print(galois.GF2)
<class 'numpy.ndarray' over GF(2)>

# The GF class factory for an order of 2 returns `galois.GF2`
In [2]: GF2 = galois.GF(2); print(GF2)
<class 'numpy.ndarray' over GF(2)>

In [3]: GF2 is galois.GF2
Out[3]: True
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

Various Galois field properties are accessible as class attributes.

In [4]: print(galois.GF2)
<class 'numpy.ndarray' over GF(2)>

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

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

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

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

Construct arrays over \(\mathrm{GF}(2)\).

In [9]: a = galois.GF2([1,0,1,1]); a
Out[9]: GF([1, 0, 1, 1], order=2)

In [10]: b = galois.GF2([1,1,1,1]); b
Out[10]: GF([1, 1, 1, 1], order=2)

Perform array arithmetic over \(\mathrm{GF}(2)\).

# Element-wise addition
In [11]: a + b
Out[11]: GF([0, 1, 0, 0], order=2)

# Element-wise subtraction
In [12]: a - b
Out[12]: GF([0, 1, 0, 0], order=2)

# Element-wise multiplication
In [13]: a * b
Out[13]: GF([1, 0, 1, 1], order=2)

# Element-wise division
In [14]: a / b
Out[14]: GF([1, 0, 1, 1], order=2)
classmethod Elements(dtype=None)

Create a Galois field array of the field’s elements \(\{0, \dots, p^m-1\}\).

Parameters

dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of all the field’s elements.

Return type

galois.GFArray

Examples

In [1]: GF = galois.GF(31)

In [2]: GF.Elements()
Out[2]: 
GF([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16,
    17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30], order=31)
classmethod Ones(shape, dtype=None)

Create a Galois field array with all ones.

Parameters

  • shape (tuple) – A numpy-compliant shape tuple, see numpy.ndarray.shape. An empty tuple () represents a scalar. A single integer or 1-tuple, e.g. N or (N,), represents the size of a 1-dim array. An n-tuple, e.g. (M,N), represents an n-dim array with each element indicating the size in each dimension.

  • dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of ones.

Return type

galois.GFArray

Examples

In [1]: GF = galois.GF(31)

In [2]: GF.Ones((2,5))
Out[2]: 
GF([[1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1]], order=31)
classmethod Random(shape=(), low=0, high=None, dtype=None)

Create a Galois field array with random field elements.

Parameters

  • shape (tuple) – A numpy-compliant shape tuple, see numpy.ndarray.shape. An empty tuple () represents a scalar. A single integer or 1-tuple, e.g. N or (N,), represents the size of a 1-dim array. An n-tuple, e.g. (M,N), represents an n-dim array with each element indicating the size in each dimension.

  • low (int, optional) – The lowest value (inclusive) of a random field element. The default is 0.

  • high (int, optional) – The highest value (exclusive) of a random field element. The default is None which represents the field’s order \(p^m\).

  • dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of random field elements.

Return type

galois.GFArray

Examples

In [1]: GF = galois.GF(31)

In [2]: GF.Random((2,5))
Out[2]: 
GF([[15,  7, 21, 21, 24],
    [19, 25, 15, 30, 28]], order=31)
classmethod Range(start, stop, step=1, dtype=None)

Create a Galois field array with a range of field elements.

Parameters

  • start (int) – The starting value (inclusive).

  • stop (int) – The stopping value (exclusive).

  • step (int, optional) – The space between values. The default is 1.

  • dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of a range of field elements.

Return type

galois.GFArray

Examples

In [1]: GF = galois.GF(31)

In [2]: GF.Range(10,20)
Out[2]: GF([10, 11, 12, 13, 14, 15, 16, 17, 18, 19], order=31)
classmethod Zeros(shape, dtype=None)

Create a Galois field array with all zeros.

Parameters

  • shape (tuple) – A numpy-compliant shape tuple, see numpy.ndarray.shape. An empty tuple () represents a scalar. A single integer or 1-tuple, e.g. N or (N,), represents the size of a 1-dim array. An n-tuple, e.g. (M,N), represents an n-dim array with each element indicating the size in each dimension.

  • dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of zeros.

Return type

galois.GFArray

Examples

In [1]: GF = galois.GF(31)

In [2]: GF.Zeros((2,5))
Out[2]: 
GF([[0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]], order=31)
classmethod display(mode='int', poly_var='x')

Sets the printing mode for arrays.

Parameters

  • mode (str, optional) – The field element display mode, either "int" (default) or "poly".

  • poly_var (str, optional) – The polynomial representation’s variable. The default is "x".

Examples

Change the display mode by calling the galois.GFArray.display method.

In [1]: GF = galois.GF(2**3)

In [2]: a = GF.Random(4); a
Out[2]: GF([5, 2, 5, 6], order=2^3)

In [3]: GF.display("poly"); a
Out[3]: GF([x^2 + 1, x, x^2 + 1, x^2 + x], order=2^3)

In [4]: GF.display("poly", "r"); a
Out[4]: GF([r^2 + 1, r, r^2 + 1, r^2 + r], order=2^3)

# Reset the print mode
In [5]: GF.display(); a
Out[5]: GF([5, 2, 5, 6], order=2^3)

The galois.GFArray.display method can also be used as a context manager.

# The original display mode
In [6]: print(a)
GF([5, 2, 5, 6], order=2^3)

# The new display context
In [7]: with GF.display("poly"):
   ...:     print(a)
   ...: 
GF([x^2 + 1, x, x^2 + 1, x^2 + x], order=2^3)

# Returns to the original display mode
In [8]: print(a)
GF([5, 2, 5, 6], order=2^3)
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 = GF(1, order=2)

The primitive element \(\alpha\) 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. 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, GF(2))

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", "calculate", "object".

Type

str

ufunc_target = 'cpu'

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

Type

str

class galois.GFArray(array, dtype=None, copy=True, order='K', ndmin=0)[source]

Bases: numpy.ndarray

Create an array over \(\mathrm{GF}(p^m)\).

The galois.GFArray class is a parent class for all Galois field array classes. Any Galois field \(\mathrm{GF}(p^m)\) with prime characteristic \(p\) and positive integer \(m\), can be constructed by calling the class factory galois.GF(p**m).

Warning

This is an abstract base class for all Galois field array classes. galois.GFArray cannot be instantiated directly. Instead, Galois field array classes are created using galois.GF.

For example, one can create the \(\mathrm{GF}(7)\) field array class as follows:

In [1]: GF7 = galois.GF(7)

In [2]: print(GF7)
<class 'numpy.ndarray' over GF(7)>

This subclass can then be used to instantiate arrays over \(\mathrm{GF}(7)\).

In [3]: GF7([3,5,0,2,1])
Out[3]: GF([3, 5, 0, 2, 1], order=7)

In [4]: GF7.Random((2,5))
Out[4]: 
GF([[5, 5, 0, 0, 5],
    [3, 1, 6, 5, 3]], order=7)

galois.GFArray is a subclass of numpy.ndarray. The galois.GFArray constructor has the same syntax as numpy.array. The returned galois.GFArray object is an array that can be acted upon like any other numpy array.

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 copy keyword argument from numpy.array. Setting dtype will explicitly set the data type of each element. The default is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

  • copy (bool, optional) – The copy keyword argument from numpy.array. The default is True which makes a copy of the input object is it’s an array.

  • order (str, optional) – The order keyword argument from numpy.array. Valid values are "K" (default), "A", "C", or "F".

  • ndmin (int, optional) – The ndmin keyword argument from numpy.array. The minimum number of dimensions of the output. The default is 0.

Returns

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

Return type

galois.GFArray

Examples

Construct various kinds of Galois fields using galois.GF.

# Construct a GF(2^m) class
In [5]: GF256 = galois.GF(2**8); print(GF256)
<class 'numpy.ndarray' over GF(2^8)>

# Construct a GF(p) class
In [6]: GF571 = galois.GF(571); print(GF571)
<class 'numpy.ndarray' over GF(571)>

# Construct a very large GF(2^m) class
In [7]: GF2m = galois.GF(2**100); print(GF2m)
<class 'numpy.ndarray' over GF(2^100)>

# Construct a very large GF(p) class
In [8]: GFp = galois.GF(36893488147419103183); print(GFp)
<class 'numpy.ndarray' over GF(36893488147419103183)>

Depending on the field’s order (size), only certain dtype values will be supported.

In [9]: GF256.dtypes
Out[9]: 
[numpy.uint8,
 numpy.uint16,
 numpy.uint32,
 numpy.int16,
 numpy.int32,
 numpy.int64]

In [10]: GF571.dtypes
Out[10]: [numpy.uint16, numpy.uint32, numpy.int16, numpy.int32, numpy.int64]

Very large fields, which can’t be represented using np.int64, can only be represented as dtype=np.object_.

In [11]: GF2m.dtypes
Out[11]: [numpy.object_]

In [12]: GFp.dtypes
Out[12]: [numpy.object_]

Newly-created arrays will use the smallest, valid dtype.

In [13]: a = GF256.Random(10); a
Out[13]: GF([ 48, 213,   4, 235, 134, 135,  74, 177, 116, 174], order=2^8)

In [14]: a.dtype
Out[14]: dtype('uint8')

This can be explicitly set by specifying the dtype keyword argument.

In [15]: a = GF256.Random(10, dtype=np.uint32); a
Out[15]: GF([252,  29,  95,  30, 115,  10,  23, 153, 186, 196], order=2^8)

In [16]: a.dtype
Out[16]: dtype('uint32')

Arrays can also be created explicitly by converting an “array-like” object.

# Construct a Galois field array from a list
In [17]: l = [142, 27, 92, 253, 103]; l
Out[17]: [142, 27, 92, 253, 103]

In [18]: GF256(l)
Out[18]: GF([142,  27,  92, 253, 103], order=2^8)

# Construct a Galois field array from an existing numpy array
In [19]: x_np = np.array(l, dtype=np.int64); x_np
Out[19]: array([142,  27,  92, 253, 103])

In [20]: GF256(l)
Out[20]: GF([142,  27,  92, 253, 103], order=2^8)

Arrays can also be created by “view casting” from an existing numpy array. This avoids a copy operation, which is especially useful for large data already brought into memory.

In [21]: a = x_np.view(GF256); a
Out[21]: GF([142,  27,  92, 253, 103], order=2^8)

# Changing `x_np` will change `a`
In [22]: x_np[0] = 0; x_np
Out[22]: array([  0,  27,  92, 253, 103])

In [23]: a
Out[23]: GF([  0,  27,  92, 253, 103], order=2^8)
classmethod Elements(dtype=None)[source]

Create a Galois field array of the field’s elements \(\{0, \dots, p^m-1\}\).

Parameters

dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of all the field’s elements.

Return type

galois.GFArray

Examples

In [1]: GF = galois.GF(31)

In [2]: GF.Elements()
Out[2]: 
GF([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16,
    17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30], order=31)
classmethod Ones(shape, dtype=None)[source]

Create a Galois field array with all ones.

Parameters

  • shape (tuple) – A numpy-compliant shape tuple, see numpy.ndarray.shape. An empty tuple () represents a scalar. A single integer or 1-tuple, e.g. N or (N,), represents the size of a 1-dim array. An n-tuple, e.g. (M,N), represents an n-dim array with each element indicating the size in each dimension.

  • dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of ones.

Return type

galois.GFArray

Examples

In [1]: GF = galois.GF(31)

In [2]: GF.Ones((2,5))
Out[2]: 
GF([[1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1]], order=31)
classmethod Random(shape=(), low=0, high=None, dtype=None)[source]

Create a Galois field array with random field elements.

Parameters

  • shape (tuple) – A numpy-compliant shape tuple, see numpy.ndarray.shape. An empty tuple () represents a scalar. A single integer or 1-tuple, e.g. N or (N,), represents the size of a 1-dim array. An n-tuple, e.g. (M,N), represents an n-dim array with each element indicating the size in each dimension.

  • low (int, optional) – The lowest value (inclusive) of a random field element. The default is 0.

  • high (int, optional) – The highest value (exclusive) of a random field element. The default is None which represents the field’s order \(p^m\).

  • dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of random field elements.

Return type

galois.GFArray

Examples

In [1]: GF = galois.GF(31)

In [2]: GF.Random((2,5))
Out[2]: 
GF([[14, 20, 13, 15, 20],
    [20, 24, 29,  3, 15]], order=31)
classmethod Range(start, stop, step=1, dtype=None)[source]

Create a Galois field array with a range of field elements.

Parameters

  • start (int) – The starting value (inclusive).

  • stop (int) – The stopping value (exclusive).

  • step (int, optional) – The space between values. The default is 1.

  • dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of a range of field elements.

Return type

galois.GFArray

Examples

In [1]: GF = galois.GF(31)

In [2]: GF.Range(10,20)
Out[2]: GF([10, 11, 12, 13, 14, 15, 16, 17, 18, 19], order=31)
classmethod Zeros(shape, dtype=None)[source]

Create a Galois field array with all zeros.

Parameters

  • shape (tuple) – A numpy-compliant shape tuple, see numpy.ndarray.shape. An empty tuple () represents a scalar. A single integer or 1-tuple, e.g. N or (N,), represents the size of a 1-dim array. An n-tuple, e.g. (M,N), represents an n-dim array with each element indicating the size in each dimension.

  • dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest valid dtype for this field class, i.e. cls.dtypes[0].

Returns

A Galois field array of zeros.

Return type

galois.GFArray

Examples

In [1]: GF = galois.GF(31)

In [2]: GF.Zeros((2,5))
Out[2]: 
GF([[0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]], order=31)
classmethod display(mode='int', poly_var='x')[source]

Sets the printing mode for arrays.

Parameters

  • mode (str, optional) – The field element display mode, either "int" (default) or "poly".

  • poly_var (str, optional) – The polynomial representation’s variable. The default is "x".

Examples

Change the display mode by calling the galois.GFArray.display method.

In [1]: GF = galois.GF(2**3)

In [2]: a = GF.Random(4); a
Out[2]: GF([0, 5, 2, 7], order=2^3)

In [3]: GF.display("poly"); a
Out[3]: GF([0, x^2 + 1, x, x^2 + x + 1], order=2^3)

In [4]: GF.display("poly", "r"); a
Out[4]: GF([0, r^2 + 1, r, r^2 + r + 1], order=2^3)

# Reset the print mode
In [5]: GF.display(); a
Out[5]: GF([0, 5, 2, 7], order=2^3)

The galois.GFArray.display method can also be used as a context manager.

# The original display mode
In [6]: print(a)
GF([0, 5, 2, 7], order=2^3)

# The new display context
In [7]: with GF.display("poly"):
   ...:     print(a)
   ...: 
GF([0, x^2 + 1, x, x^2 + x + 1], order=2^3)

# Returns to the original display mode
In [8]: print(a)
GF([0, 5, 2, 7], order=2^3)
classmethod target(target, mode, rebuild=False)[source]

Retarget the just-in-time compiled numba ufuncs.

alpha = None

The primitive element \(\alpha\) 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 = None

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 = None

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

Type

int

dtypes = []

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

Type

list

order = None

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 = None

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 = None

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

Type

str

ufunc_target = None

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

Type

str

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

Bases: object

Create a polynomial \(p(x)\) over \(\mathrm{GF}(q)\).

The polynomial \(p(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\) has coefficients \(\{a_{d}, a_{d-1}, \dots, a_1, a_0\}\) in \(\mathrm{GF}(q)\).

Parameters

  • coeffs (array_like) – List of polynomial coefficients \(\{a_{d}, a_{d-1}, \dots, a_1, a_0\}\) with type galois.GFArray, numpy.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.GFArray, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default is None which represents galois.GF2. If coeffs is a Galois field array, then that field is used and the field argument 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^{d}\)) and the last element is the 0-th degree element \(x^0\).

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Create a polynomial over \(\mathrm{GF}(2)\).

In [1]: galois.Poly([1,0,1,1])
Out[1]: Poly(x^3 + x + 1, GF(2))

In [2]: galois.Poly.Degrees([3,1,0])
Out[2]: Poly(x^3 + x + 1, GF(2))

Create a polynomial over \(\mathrm{GF}(2^8)\).

In [3]: GF = galois.GF(2**8)

In [4]: galois.Poly([124,0,223,0,0,15], field=GF)
Out[4]: Poly(124x^5 + 223x^3 + 15, GF(2^8))

# Alternate way of constructing the same polynomial
In [5]: galois.Poly.Degrees([5,3,0], coeffs=[124,223,15], field=GF)
Out[5]: Poly(124x^5 + 223x^3 + 15, GF(2^8))

Polynomial arithmetic using binary operators.

In [6]: a = galois.Poly([117,0,63,37], field=GF); a
Out[6]: Poly(117x^3 + 63x + 37, GF(2^8))

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

In [8]: a + b
Out[8]: Poly(117x^3 + 224x^2 + 63x + 48, GF(2^8))

In [9]: a - b
Out[9]: Poly(117x^3 + 224x^2 + 63x + 48, GF(2^8))

# Compute the quotient of the polynomial division
In [10]: a / b
Out[10]: Poly(202x, GF(2^8))

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

# Compute the remainder of the polynomial division
In [12]: a % b
Out[12]: Poly(198x + 37, GF(2^8))

# Compute both the quotient and remainder in one pass
In [13]: divmod(a, b)
Out[13]: (Poly(202x, GF(2^8)), Poly(198x + 37, GF(2^8)))
classmethod Coeffs(coeffs, field=None, order='desc')[source]

Constructs a polynomial over \(\mathrm{GF}(q)\) from its coefficients.

Alias of galois.Poly constructor.

Parameters

  • coeffs (array_like) – List of polynomial coefficients \(\{a_{d}, a_{d-1}, \dots, a_1, a_0\}\) with type galois.GFArray, numpy.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.GFArray, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default is None which represents galois.GF2. If coeffs is a Galois field array, then that field is used and the field argument 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^{d}\)) and the last element is the 0-th degree element \(x^0\).

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

classmethod Degrees(degrees, coeffs=None, field=None)[source]

Constructs a polynomial over \(\mathrm{GF}(q)\) from its non-zero degrees.

Parameters

  • degrees (list) – List of polynomial degrees with non-zero coefficients.

  • coeffs (array_like, optional) – List of corresponding non-zero coefficients. The default is None which corresponds to all one coefficients, i.e. [1,]*len(degrees).

  • field (galois.GFArray, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default is`None` which represents galois.GF2.

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Construct a polynomial over \(\mathrm{GF}(2)\) by specifying the degrees with non-zero coefficients.

In [1]: galois.Poly.Degrees([3,1,0])
Out[1]: Poly(x^3 + x + 1, GF(2))

Construct a polynomial over \(\mathrm{GF}(2^8)\) by specifying the degrees with non-zero coefficients.

In [2]: GF = galois.GF(2**8)

In [3]: galois.Poly.Degrees([3,1,0], coeffs=[251,73,185], field=GF)
Out[3]: Poly(251x^3 + 73x + 185, GF(2^8))
classmethod Identity(field=<class 'galois.gf2.GF2'>)[source]

Constructs the identity polynomial \(p(x) = x\) over \(\mathrm{GF}(q)\).

Parameters

field (galois.GFArray, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default is galois.GF2.

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Construct the identity polynomial over \(\mathrm{GF}(2)\).

In [1]: galois.Poly.Identity()
Out[1]: Poly(x, GF(2))

Construct the identity polynomial over \(\mathrm{GF}(2^8)\).

In [2]: GF = galois.GF(2**8)

In [3]: galois.Poly.Identity(field=GF)
Out[3]: Poly(x, GF(2^8))
classmethod Integer(integer, field=<class 'galois.gf2.GF2'>)[source]

Constructs a polynomial over \(\mathrm{GF}(q)\) from its integer representation.

The integer value \(i\) represents the polynomial \(p(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\) over field \(\mathrm{GF}(q)\) if \(i = a_{d}q^{d} + a_{d-1}q^{d-1} + \dots + a_1q + a_0\) using integer arithmetic, not finite field arithmetic.

Parameters

  • integer (int) – The integer representation of the polynomial \(p(x)\).

  • field (galois.GFArray, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default is galois.GF2.

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Construct a polynomial over \(\mathrm{GF}(2)\) from its integer representation.

In [1]: galois.Poly.Integer(5)
Out[1]: Poly(x^2 + 1, GF(2))

Construct a polynomial over \(\mathrm{GF}(2^8)\) from its integer representation.

In [2]: GF = galois.GF(2**8)

In [3]: galois.Poly.Integer(13*256**3 + 117, field=GF)
Out[3]: Poly(13x^3 + 117, GF(2^8))
classmethod One(field=<class 'galois.gf2.GF2'>)[source]

Constructs the one polynomial \(p(x) = 1\) over \(\mathrm{GF}(q)\).

Parameters

field (galois.GFArray, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default is galois.GF2.

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Construct the one polynomial over \(\mathrm{GF}(2)\).

In [1]: galois.Poly.One()
Out[1]: Poly(1, GF(2))

Construct the one polynomial over \(\mathrm{GF}(2^8)\).

In [2]: GF = galois.GF(2**8)

In [3]: galois.Poly.One(field=GF)
Out[3]: Poly(1, GF(2^8))
classmethod Random(degree, field=<class 'galois.gf2.GF2'>)[source]

Constructs a random polynomial over \(\mathrm{GF}(q)\) with degree \(d\).

Parameters

  • degree (int) – The degree of the polynomial.

  • field (galois.GFArray, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default is galois.GF2.

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Construct a random degree-\(5\) polynomial over \(\mathrm{GF}(2)\).

In [1]: galois.Poly.Random(5)
Out[1]: Poly(x^5 + x^2 + 1, GF(2))

Construct a random degree-\(5\) polynomial over \(\mathrm{GF}(2^8)\).

In [2]: GF = galois.GF(2**8)

In [3]: galois.Poly.Random(5, field=GF)
Out[3]: Poly(77x^5 + 180x^4 + 239x^3 + 176x^2 + 166x + 94, GF(2^8))
classmethod Roots(roots, multiplicities=None, field=None)[source]

Constructs a monic polynomial in \(\mathrm{GF}(q)[x]\) from its roots.

The polynomial \(p(x)\) with \(d\) roots \(\{r_0, r_1, \dots, r_{d-1}\}\) is:

\[ \begin{align}\begin{aligned}p(x) &= (x - r_0) (x - r_1) \dots (x - r_{d-1})\\p(x) &= a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\end{aligned}\end{align} \]
Parameters

  • roots (array_like) – List of roots in \(\mathrm{GF}(q)\) of the desired polynomial.

  • multiplicities (array_like, optional) – List of multiplicity of each root. The default is None which corresponds to all ones.

  • field (galois.GFArray, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default is`None` which represents galois.GF2.

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Construct a polynomial over \(\mathrm{GF}(2)\) from a list of its roots.

In [1]: roots = [0, 0, 1]

In [2]: p = galois.Poly.Roots(roots); p
Out[2]: Poly(x^3 + x^2, GF(2))

In [3]: p(roots)
Out[3]: GF([0, 0, 0], order=2)

Construct a polynomial over \(\mathrm{GF}(2^8)\) from a list of its roots.

In [4]: GF = galois.GF(2**8)

In [5]: roots = [121, 198, 225]

In [6]: p = galois.Poly.Roots(roots, field=GF); p
Out[6]: Poly(x^3 + 94x^2 + 174x + 89, GF(2^8))

In [7]: p(roots)
Out[7]: GF([0, 0, 0], order=2^8)
classmethod Zero(field=<class 'galois.gf2.GF2'>)[source]

Constructs the zero polynomial \(p(x) = 0\) over \(\mathrm{GF}(q)\).

Parameters

field (galois.GFArray, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default is galois.GF2.

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Construct the zero polynomial over \(\mathrm{GF}(2)\).

In [1]: galois.Poly.Zero()
Out[1]: Poly(0, GF(2))

Construct the zero polynomial over \(\mathrm{GF}(2^8)\).

In [2]: GF = galois.GF(2**8)

In [3]: galois.Poly.Zero(field=GF)
Out[3]: Poly(0, GF(2^8))
derivative(k=1)[source]

Computes the \(k\)-th formal derivative \(\frac{d^k}{dx^k} p(x)\) of the polynomial \(p(x)\).

For the polynomial

\[p(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\]

the first formal derivative is defined as

\[p'(x) = (d) \cdot a_{d} x^{d-1} + (d-1) \cdot a_{d-1} x^{d-2} + \dots + (2) \cdot a_{2} x + a_1\]

where \(\cdot\) represents scalar multiplication (repeated addition), not finite field multiplication, e.g. \(3 \cdot a = a + a + a\).

Parameters

k (int, optional) – The number of derivatives to compute. 1 corresponds to \(p'(x)\), 2 corresponds to \(p''(x)\), etc. The default is 1.

Returns

The \(k\)-th formal derivative of the polynomial \(p(x)\).

Return type

galois.Poly

References

Examples

Compute the derivatives of a polynomial over \(\mathrm{GF}(2)\).

In [1]: p = galois.Poly.Random(7); p
Out[1]: Poly(x^7 + x^6 + x^5 + x^3 + x^2 + x + 1, GF(2))

In [2]: p.derivative()
Out[2]: Poly(x^6 + x^4 + x^2 + 1, GF(2))

# k derivatives of a polynomial where k is the Galois field's characteristic will always result in 0
In [3]: p.derivative(2)
Out[3]: Poly(0, GF(2))

Compute the derivatives of a polynomial over \(\mathrm{GF}(7)\).

In [4]: GF = galois.GF(7)

In [5]: p = galois.Poly.Random(11, field=GF); p
Out[5]: Poly(2x^11 + x^8 + 3x^7 + 5x^6 + 5x^5 + 3x^4 + 5x^3 + 2x^2 + x + 1, GF(7))

In [6]: p.derivative()
Out[6]: Poly(x^10 + x^7 + 2x^5 + 4x^4 + 5x^3 + x^2 + 4x + 1, GF(7))

In [7]: p.derivative(2)
Out[7]: Poly(3x^9 + 3x^4 + 2x^3 + x^2 + 2x + 4, GF(7))

In [8]: p.derivative(3)
Out[8]: Poly(6x^8 + 5x^3 + 6x^2 + 2x + 2, GF(7))

# k derivatives of a polynomial where k is the Galois field's characteristic will always result in 0
In [9]: p.derivative(7)
Out[9]: Poly(0, GF(2))

Compute the derivatives of a polynomial over \(\mathrm{GF}(2^8)\).

In [10]: GF = galois.GF(2**8)

In [11]: p = galois.Poly.Random(7, field=GF); p
Out[11]: Poly(148x^7 + 185x^6 + 66x^5 + 133x^4 + 181x^3 + 159x^2 + 208x + 246, GF(2^8))

In [12]: p.derivative()
Out[12]: Poly(148x^6 + 66x^4 + 181x^2 + 208, GF(2^8))

# k derivatives of a polynomial where k is the Galois field's characteristic will always result in 0
In [13]: p.derivative(2)
Out[13]: Poly(0, GF(2^8))
roots(multiplicity=False)[source]

Calculates the roots \(r\) of the polynomial \(p(x)\), such that \(p(r) = 0\).

This implementation uses Chien’s search to find the roots \(\{r_0, r_1, \dots, r_{k-1}\}\) of the degree-\(d\) polynomial

\[p(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0,\]

where \(k \le d\). Then, \(p(x)\) can be factored as

\[p(x) = (x - r_0)^{m_0} (x - r_1)^{m_1} \dots (x - r_{k-1})^{m_{k-1}},\]

where \(m_i\) is the multiplicity of root \(r_i\) and

\[\sum_{i=0}^{k-1} m_i = d.\]

The Galois field elements can be represented as \(\mathrm{GF}(q) = \{0, 1, \alpha, \alpha^2, \dots, \alpha^{q-2}\}\), where \(\alpha\) is a primitive element of \(\mathrm{GF}(q)\).

\(0\) is a root of \(p(x)\) if:

\[a_0 = 0\]

\(1\) is a root of \(p(x)\) if:

\[\sum_{j=0}^{d} a_j = 0\]

The remaining elements of \(\mathrm{GF}(q)\) are powers of \(\alpha\). The following equations calculate \(p(\alpha^i)\), where \(\alpha^i\) is a root of \(p(x)\) if \(p(\alpha^i) = 0\).

\[ \begin{align}\begin{aligned}p(\alpha^i) &= a_{d}(\alpha^i)^{d} + a_{d-1}(\alpha^i)^{d-1} + \dots + a_1(\alpha^i) + a_0\\p(\alpha^i) &\overset{\Delta}{=} \lambda_{i,d} + \lambda_{i,d-1} + \dots + \lambda_{i,1} + \lambda_{i,0}\\p(\alpha^i) &= \sum_{j=0}^{d} \lambda_{i,j}\end{aligned}\end{align} \]

The next power of \(\alpha\) can be easily calculated from the previous calculation.

\[ \begin{align}\begin{aligned}p(\alpha^{i+1}) &= a_{d}(\alpha^{i+1})^{d} + a_{d-1}(\alpha^{i+1})^{d-1} + \dots + a_1(\alpha^{i+1}) + a_0\\p(\alpha^{i+1}) &= a_{d}(\alpha^i)^{d}\alpha^d + a_{d-1}(\alpha^i)^{d-1}\alpha^{d-1} + \dots + a_1(\alpha^i)\alpha + a_0\\p(\alpha^{i+1}) &= \lambda_{i,d}\alpha^d + \lambda_{i,d-1}\alpha^{d-1} + \dots + \lambda_{i,1}\alpha + \lambda_{i,0}\\p(\alpha^{i+1}) &= \sum_{j=0}^{d} \lambda_{i,j}\alpha^j\end{aligned}\end{align} \]
Parameters

multiplicity (bool, optional) – Optionally return the multiplicity of each root. The default is False, which only returns the unique roots.

Returns

  • galois.GFArray – Galois field array of roots of \(p(x)\).

  • np.ndarray – The multiplicity of each root. Only returned if multiplicity=True.

References

Examples

Find the roots of a polynomial over \(\mathrm{GF}(2)\).

In [1]: p = galois.Poly.Roots([0,]*7 + [1,]*13); p
Out[1]: Poly(x^20 + x^19 + x^16 + x^15 + x^12 + x^11 + x^8 + x^7, GF(2))

In [2]: p.roots()
Out[2]: GF([0, 1], order=2)

In [3]: p.roots(multiplicity=True)
Out[3]: (GF([0, 1], order=2), array([ 7, 13]))

Find the roots of a polynomial over \(\mathrm{GF}(2^8)\).

In [4]: GF = galois.GF(2**8)

In [5]: p = galois.Poly.Roots([18,]*7 + [155,]*13 + [227,]*9, field=GF); p
Out[5]: Poly(x^29 + 106x^28 + 27x^27 + 155x^26 + 230x^25 + 38x^24 + 78x^23 + 8x^22 + 46x^21 + 210x^20 + 248x^19 + 214x^18 + 172x^17 + 152x^16 + 82x^15 + 237x^14 + 172x^13 + 230x^12 + 141x^11 + 63x^10 + 103x^9 + 167x^8 + 199x^7 + 127x^6 + 254x^5 + 95x^4 + 93x^3 + 3x^2 + 4x + 208, GF(2^8))

In [6]: p.roots()
Out[6]: GF([ 18, 155, 227], order=2^8)

In [7]: p.roots(multiplicity=True)
Out[7]: (GF([ 18, 155, 227], order=2^8), array([ 7, 13,  9]))
property coeffs

The coefficients of the polynomial in degree-descending order. The entries of galois.Poly.degrees are paired with galois.Poly.coeffs.

Examples

In [1]: GF = galois.GF(7)

In [2]: p = galois.Poly([3, 0, 5, 2], field=GF)

In [3]: p.coeffs
Out[3]: GF([3, 0, 5, 2], order=7)
Type

galois.GFArray

property degree

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

Examples

In [1]: GF = galois.GF(7)

In [2]: p = galois.Poly([3, 0, 5, 2], field=GF)

In [3]: p.degree
Out[3]: 3
Type

int

property degrees

An array of the polynomial degrees in degree-descending order. The entries of galois.Poly.degrees are paired with galois.Poly.coeffs.

Examples

In [1]: GF = galois.GF(7)

In [2]: p = galois.Poly([3, 0, 5, 2], field=GF)

In [3]: p.degrees
Out[3]: array([3, 2, 1, 0])
Type

numpy.ndarray

property field

The Galois field to which the coefficients belong. The galois.Poly.field property is a subclass of galois.GFArray. This property is settable.

Examples

In [1]: GF = galois.GF(2**8)

# The primitive polynomial of the field GF(p^m) is degree-m over GF(p)[x]
In [2]: prim_poly = GF.prim_poly; prim_poly
Out[2]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))

In [3]: prim_poly.field
Out[3]: galois.gf2.GF2

# Convert the primitive polynomial from GF(p)[x] to GF(p^m)[x]
In [4]: prim_poly.field = GF; prim_poly
Out[4]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2^8))

# The primitive element alpha is a root of the primitive polynomial in GF(p^m)
In [5]: prim_poly(GF.alpha)
Out[5]: GF(0, order=2^8)
Type

type

property integer

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

Examples

In [1]: GF = galois.GF(7)

In [2]: p = galois.Poly([3, 0, 5, 2], field=GF)

In [3]: p.integer
Out[3]: 1066

In [4]: p.integer == 3*7**3 + 5*7**1 + 2*7**0
Out[4]: True
Type

int

property nonzero_coeffs

The non-zero coefficients of the polynomial in degree-descending order. The entries of galois.Poly.nonzero_degrees are paired with galois.Poly.nonzero_coeffs.

Examples

In [1]: GF = galois.GF(7)

In [2]: p = galois.Poly([3, 0, 5, 2], field=GF)

In [3]: p.nonzero_coeffs
Out[3]: GF([3, 5, 2], order=7)
Type

galois.GFArray

property nonzero_degrees

An array of the polynomial degrees that have non-zero coefficients, in degree-descending order. The entries of galois.Poly.nonzero_degrees are paired with galois.Poly.nonzero_coeffs.

Examples

In [1]: GF = galois.GF(7)

In [2]: p = galois.Poly([3, 0, 5, 2], field=GF)

In [3]: p.nonzero_degrees
Out[3]: array([3, 1, 0])
Type

numpy.ndarray

galois.GF(order, 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

  • order (int) – The order \(p^m\) of the field \(\mathrm{GF}(p^m)\). Order must be a prime power.

  • 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 array class that is a subclass of galois.GFArray.

Return type

type

Examples

Construct various Galois field array classes.

# Construct a GF(2^m) class
In [1]: GF256 = galois.GF(2**8); print(GF256)
<class 'numpy.ndarray' over GF(2^8)>

# Construct a GF(p) class
In [2]: GF571 = galois.GF(571); print(GF571)
<class 'numpy.ndarray' over GF(571)>

# Construct a very large GF(2^m) class
In [3]: GF2m = galois.GF(2**100); print(GF2m)
<class 'numpy.ndarray' over GF(2^100)>

# Construct a very large GF(p) class
In [4]: GFp = galois.GF(36893488147419103183); print(GFp)
<class 'numpy.ndarray' over GF(36893488147419103183)>

See galois.GFArray for more examples of what Galois field arrays can do.

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 math.gcd(i, n) == 1]; totatives
Out[3]: [1, 3, 7, 9, 11, 13, 17, 19]

In [4]: for a in totatives:
   ...:     result = pow(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} = {ai} (mod {m[i]}), Valid congruence: {ai == a[i]}")
   ...: 
39 = 0 (mod 3), Valid congruence: True
39 = 3 (mod 4), Valid congruence: True
39 = 4 (mod 5), Valid congruence: True
galois.conway_poly(p, n)[source]

Returns the degree-\(n\) Conway polynomial \(C_{p,n}\) over \(\mathrm{GF}(p)\).

A Conway polynomial is a an irreducible polynomial over \(\mathrm{GF}(p)\) that provides a standard representation of \(\mathrm{GF}(p^n)\) as a splitting field of \(C_{p,n}\). Conway polynomials provide compatability between fields and their subfields, and hence are the common way to represent extension fields.

The Conway polynomial \(C_{p,n}\) is defined as the lexicographically-minimal monic irreducible polynomial of degree \(n\) over \(\mathrm{GF}(p)\) that is compatible with all \(C_{p,m}\), for \(m\) dividing \(n\).

This function uses Frank Luebeck’s Conway polynomial database for fast lookup, not construction.

Parameters

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

  • n (int) – The degree \(n\) of the Conway polynomial.

Returns

The degree-\(n\) Conway polynomial \(C_{p,n}\) over \(\mathrm{GF}(p)\).

Return type

galois.Poly

Raises

LookupError – If the Conway polynomial \(C_{p,n}\) is not found in Frank Luebeck’s database.

Warning

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, GF(2))

In [2]: galois.conway_poly(7, 13)
Out[2]: Poly(x^13 + 6x^2 + 4, GF(7))
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 coprime with n
In [3]: totatives = [k for k in range(n) if math.gcd(k, 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.factors(n)[source]

Returns the positive factors of the integer \(n\).

Parameters

n (int) – An integer to be factored.

Returns

Sorted array of factors of \(n\).

Return type

list

Examples

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

Probabilistic primality test of \(n\).

This function implements Fermat’s primality test. The test says that for an integer \(n\), select an integer \(a\) coprime with \(n\). If \(a^{n-1} \equiv 1 (\textrm{mod}\ n)\), then \(n\) is prime or pseudoprime.

Parameters

n (int) – A positive integer.

Returns

False if \(n\) is known to be composite. True if \(n\) is prime or pseudoprime.

Return type

bool

Examples

# List of some primes
In [1]: primes = [257, 24841, 65497]

In [2]: for prime in primes:
   ...:     is_prime = galois.fermat_primality_test(prime)
   ...:     p, k = galois.prime_factors(prime)
   ...:     print("Prime = {:5d}, Fermat's Prime Test = {}, Prime factors = {}".format(prime, is_prime, list(p)))
   ...: 
Prime =   257, Fermat's Prime Test = True, Prime factors = [257]
Prime = 24841, Fermat's Prime Test = True, Prime factors = [24841]
Prime = 65497, Fermat's Prime Test = True, Prime factors = [65497]

# List of some strong pseudoprimes with base 2
In [3]: pseudoprimes = [2047, 29341, 65281]

In [4]: for pseudoprime in pseudoprimes:
   ...:     is_prime = galois.fermat_primality_test(pseudoprime)
   ...:     p, k = galois.prime_factors(pseudoprime)
   ...:     print("Pseudoprime = {:5d}, Fermat's Prime Test = {}, Prime factors = {}".format(pseudoprime, is_prime, list(p)))
   ...: 
Pseudoprime =  2047, Fermat's Prime Test = True, Prime factors = [23, 89]
Pseudoprime = 29341, Fermat's Prime Test = True, Prime factors = [13, 37, 61]
Pseudoprime = 65281, Fermat's Prime Test = True, Prime factors = [97, 673]
galois.gcd(a, b)[source]

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

This implementation uses the Extended Euclidean Algorithm.

Parameters

  • a (int) – Any integer.

  • b (int) – Any integer.

Returns

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

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

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

References

Examples

In [1]: a = 2

In [2]: b = 13

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

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

In [5]: a*x + b*y == gcd
Out[5]: True
galois.is_cyclic(n)[source]

Determines whether the multiplicative group \(\mathbb{Z}{_n^\times}\) is cyclic.

The multiplicative group \(\mathbb{Z}{_n^\times}\) is the set of positive integers \(1 \le a < n\) that are coprime with \(n\). \(\mathbb{Z}{_n^\times}\) being cyclic means that some primitive root (or generator) \(g\) can generate the group \(\mathbb{Z}{_n^\times} = \{g, g^2, \dots, g^k\}\), where \(k\) is order of the group. The order of the group is defined by Euler’s totient function, \(\phi(n) = k\). If \(\mathbb{Z}{_n^\times}\) is cyclic, the number of primitive roots is found by \(\phi(k)\) or \(\phi(\phi(n))\).

\(\mathbb{Z}{_n^\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.

Parameters

n (int) – A positive integer.

Returns

True if the multiplicative group \(\mathbb{Z}{_n^\times}\) is cyclic.

Return type

bool

References

Examples

The elements of \(\mathbb{Z}{_n^\times}\) are the positive integers less than \(n\) that are coprime with \(n\). For example when \(n = 14\), then \(\mathbb{Z}{_{14}^\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_totient(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

# To find the primitive roots 3 and 5, you can just call `primitive_roots()`
In [7]: roots = list(galois.primitive_roots(n)); roots
Out[7]: [3, 5]

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

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

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

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

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

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

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

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

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

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

Checks whether the polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is irreducible.

This function implementats Rabin’s irreducibility test. It says a degree-\(n\) polynomial \(f(x)\) over \(\mathrm{GF}(p)\) for prime \(p\) is irreducible if and only if \(f(x)\ |\ (x^{p^n} - x)\) and \(\textrm{gcd}(f(x),\ x^{p^{m_i}} - x) = 1\) for \(1 \le i \le k\), where \(m_i = n/p_i\) for the \(k\) prime divisors \(p_i\) of \(n\).

Parameters

poly (galois.Poly) – A polynomial \(f(x)\) over \(\mathrm{GF}(p)\).

Returns

True if the polynomial is irreducible.

Return type

bool

References

galois.is_prime(n)[source]

Determines if \(n\) is prime.

This algorithm will first run Fermat’s primality test to check \(n\) for compositeness. If it determines \(n\) is composite, the function will quickly return. If Fermat’s primality test returns True, then \(n\) could be prime or pseudoprime. If so, then this function will run seven rounds of Miller-Rabin’s primality test. With this many rounds, a result of True should have high probability of being a true prime, not a pseudoprime.

Parameters

n (int) – A positive integer.

Returns

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

Return type

bool

Examples

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

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

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

In [3]: galois.is_prime(1000000000000000035000061)
Out[3]: True
galois.is_primitive_root(g, n)[source]

Determines if \(g\) is a 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\).

Parameters

  • g (int) – A positive integer that may be a primitive root modulo \(n\).

  • n (int) – A positive integer.

Returns

True if \(g\) is a primitive root modulo \(n\).

Return type

bool

Examples

In [1]: galois.is_primitive_root(2, 7)
Out[1]: False

In [2]: galois.is_primitive_root(3, 7)
Out[2]: True

In [3]: list(galois.primitive_roots(7))
Out[3]: [3, 5]
galois.isqrt(n)[source]

Computes the integer square root of \(n\) such that \(\textrm{isqrt}(n)^2 \le n\).

This is here for Python versions before 3.8. For Python 3.8 and later, use math.isqrt.

Parameters

n (int) – A non-negative integer

Returns

The integer square root of \(n\) such that \(\textrm{isqrt}(n)^2 \le n\).

Return type

int

Examples

# Use a large Mersenne prime
In [1]: p = galois.mersenne_primes(2000)[-1]; p
Out[1]: 10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087

In [2]: sqrt_p = galois.isqrt(p); sqrt_p
Out[2]: 3226132699481594337650229932669505772017441235628244885631123722785761803162998767122846394796285964908262519578341713326387400858087872534573955058079614218029097609909460991319304989482693499

In [3]: sqrt_p**2 <= p
Out[3]: True

In [4]: (sqrt_p + 1)**2 <= p
Out[4]: False
galois.kth_prime(k)[source]

Returns the \(k\)-th prime.

Parameters

k (int) – The prime index, where \(k = \{1,2,3,4,\dots\}\) for primes \(p = \{2,3,5,7,\dots\}\).

Returns

The \(k\)-th prime.

Return type

int

Examples

In [1]: galois.kth_prime(1)
Out[1]: 2

In [2]: galois.kth_prime(3)
Out[2]: 5

In [3]: galois.kth_prime(1000)
Out[3]: 7919
galois.mersenne_exponents(n=None)[source]

Returns all known Mersenne exponents \(e\) for \(e \le n\).

A Mersenne exponent \(e\) is an exponent of \(2\) such that \(2^e - 1\) is prime.

Parameters

n (int, optional) – The max exponent of 2. The default is None which returns all known Mersenne exponents.

Returns

The list of Mersenne exponents \(e\) for \(e \le n\).

Return type

list

References

Examples

# List all Mersenne exponents for Mersenne primes up to 4000 bits
In [1]: e = galois.mersenne_exponents(4000); e
Out[1]: 
[2,
 3,
 5,
 7,
 13,
 17,
 19,
 31,
 61,
 89,
 107,
 127,
 521,
 607,
 1279,
 2203,
 2281,
 3217]

# Select one Merseene exponent and compute its Mersenne prime
In [2]: p = 2**e[-1] - 1; p
Out[2]: 259117086013202627776246767922441530941818887553125427303974923161874019266586362086201209516800483406550695241733194177441689509238807017410377709597512042313066624082916353517952311186154862265604547691127595848775610568757931191017711408826252153849035830401185072116424747461823031471398340229288074545677907941037288235820705892351068433882986888616658650280927692080339605869308790500409503709875902119018371991620994002568935113136548829739112656797303241986517250116412703509705427773477972349821676443446668383119322540099648994051790241624056519054483690809616061625743042361721863339415852426431208737266591962061753535748892894599629195183082621860853400937932839420261866586142503251450773096274235376822938649407127700846077124211823080804139298087057504713825264571448379371125032081826126566649084251699453951887789613650248405739378594599444335231188280123660406262468609212150349937584782292237144339628858485938215738821232393687046160677362909315071

In [3]: galois.is_prime(p)
Out[3]: True

# Display all known Mersenne exponenets
In [4]: galois.mersenne_exponents()
Out[4]: 
[2,
 3,
 5,
 7,
 13,
 17,
 19,
 31,
 61,
 89,
 107,
 127,
 521,
 607,
 1279,
 2203,
 2281,
 3217,
 4253,
 4423,
 9689,
 9941,
 11213,
 19937,
 21701,
 23209,
 44497,
 86243,
 110503,
 132049,
 216091,
 756839,
 859433,
 1257787,
 1398269,
 2976221,
 3021377,
 6972593,
 13466917,
 20996011,
 24036583,
 25964951,
 30402457,
 32582657,
 37156667,
 42643801,
 43112609]
galois.mersenne_primes(n=None)[source]

Returns all known Mersenne primes \(p\) for \(p \le 2^n - 1\).

Mersenne primes are primes that are one less than a power of 2.

Parameters

n (int, optional) – The max power of 2. The default is None which returns all known Mersenne exponents.

Returns

The list of known Mersenne primes \(p\) for \(p \le 2^n - 1\).

Return type

list

References

Examples

# List all Mersenne primes up to 2000 bits
In [1]: p = galois.mersenne_primes(2000); p
Out[1]: 
[3,
 7,
 31,
 127,
 8191,
 131071,
 524287,
 2147483647,
 2305843009213693951,
 618970019642690137449562111,
 162259276829213363391578010288127,
 170141183460469231731687303715884105727,
 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151,
 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127,
 10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087]

In [2]: galois.is_prime(p[-1])
Out[2]: True
galois.miller_rabin_primality_test(n, a=None, rounds=1)[source]

Probabilistic primality test of \(n\).

This function implements the Miller-Rabin primality test. The test says that for an integer \(n\), select an integer \(a\) such that \(a < n\). Factor \(n - 1\) such that \(2^s d = n - 1\). Then, \(n\) is composite, if \(a^d \not\equiv 1 (\textrm{mod}\ n)\) and \(a^{2^r d} \not\equiv n - 1 (\textrm{mod}\ n)\) for \(1 \le r < s\).

Parameters

  • n (int) – A positive integer.

  • a (int, optional) – Initial composite witness value, \(1 \le a < n\). On subsequent rounds, \(a\) will be a different value. The default is a random value.

  • rounds (int, optional) – The number of iterations attempting to detect \(n\) as composite. Additional rounds will choose new \(a\). Sufficient rounds have arbitrarily-high probability of detecting a composite.

Returns

False if \(n\) is known to be composite. True if \(n\) is prime or pseudoprime.

Return type

bool

References

Examples

# List of some primes
In [1]: primes = [257, 24841, 65497]

In [2]: for prime in primes:
   ...:     is_prime = galois.miller_rabin_primality_test(prime)
   ...:     p, k = galois.prime_factors(prime)
   ...:     print("Prime = {:5d}, Miller-Rabin Prime Test = {}, Prime factors = {}".format(prime, is_prime, list(p)))
   ...: 
Prime =   257, Miller-Rabin Prime Test = True, Prime factors = [257]
Prime = 24841, Miller-Rabin Prime Test = True, Prime factors = [24841]
Prime = 65497, Miller-Rabin Prime Test = True, Prime factors = [65497]

# List of some strong pseudoprimes with base 2
In [3]: pseudoprimes = [2047, 29341, 65281]

# Single round of Miller-Rabin, sometimes fooled by pseudoprimes
In [4]: for pseudoprime in pseudoprimes:
   ...:     is_prime = galois.miller_rabin_primality_test(pseudoprime)
   ...:     p, k = galois.prime_factors(pseudoprime)
   ...:     print("Pseudoprime = {:5d}, Miller-Rabin Prime Test = {}, Prime factors = {}".format(pseudoprime, is_prime, list(p)))
   ...: 
Pseudoprime =  2047, Miller-Rabin Prime Test = False, Prime factors = [23, 89]
Pseudoprime = 29341, Miller-Rabin Prime Test = False, Prime factors = [13, 37, 61]
Pseudoprime = 65281, Miller-Rabin Prime Test = False, Prime factors = [97, 673]

# 7 rounds of Miller-Rabin, never fooled by pseudoprimes
In [5]: for pseudoprime in pseudoprimes:
   ...:     is_prime = galois.miller_rabin_primality_test(pseudoprime, rounds=7)
   ...:     p, k = galois.prime_factors(pseudoprime)
   ...:     print("Pseudoprime = {:5d}, Miller-Rabin Prime Test = {}, Prime factors = {}".format(pseudoprime, is_prime, list(p)))
   ...: 
Pseudoprime =  2047, Miller-Rabin Prime Test = False, Prime factors = [23, 89]
Pseudoprime = 29341, Miller-Rabin Prime Test = False, Prime factors = [13, 37, 61]
Pseudoprime = 65281, Miller-Rabin Prime Test = False, Prime factors = [97, 673]
galois.next_prime(x)[source]

Returns the nearest prime \(p\), such that \(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.poly_exp_mod(poly, power, modulus)[source]

Efficiently exponentiates a polynomial \(f(x)\) to the power \(k\) reducing by modulo \(g(x)\), \(f^k\ \textrm{mod}\ g\).

The algorithm is more efficient than exponentiating first and then reducing modulo \(g(x)\). Instead, this algorithm repeatedly squares \(f\), reducing modulo \(g\) at each step.

Parameters

  • poly (galois.Poly) – The polynomial to be exponentiated \(f(x)\).

  • power (int) – The non-negative exponent \(k\).

  • modulus (galois.Poly) – The reducing polynomial \(g(x)\).

Returns

The resulting polynomial \(h(x) = f^k\ \textrm{mod}\ g\).

Return type

galois.Poly

Examples

In [1]: GF = galois.GF(31)

In [2]: f = galois.Poly.Random(10, field=GF); f
Out[2]: Poly(9x^10 + 7x^9 + 2x^8 + 6x^7 + x^6 + 19x^5 + 10x^4 + 29x^3 + 15x^2 + 25x + 27, GF(31))

In [3]: g = galois.Poly.Random(7, field=GF); g
Out[3]: Poly(23x^7 + 10x^6 + x^5 + 18x^4 + 27x^3 + 23x^2 + 24x + 28, GF(31))

# %timeit f**200 % g
# 1.23 s ± 41.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
In [4]: f**200 % g
Out[4]: Poly(12x^6 + 7x^5 + 4x^4 + 3x^3 + 3x^2 + 7x + 11, GF(31))

# %timeit galois.poly_exp_mod(f, 200, g)
# 41.7 ms ± 468 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
In [5]: galois.poly_exp_mod(f, 200, g)
Out[5]: Poly(12x^6 + 7x^5 + 4x^4 + 3x^3 + 3x^2 + 7x + 11, GF(31))
galois.poly_gcd(a, b)[source]

Finds the greatest common divisor of two polynomials \(a(x)\) and \(b(x)\) over \(\mathrm{GF}(q)\).

This implementation uses the Extended Euclidean Algorithm.

Parameters

  • a (galois.Poly) – A polynomial \(a(x)\) over \(\mathrm{GF}(q)\).

  • b (galois.Poly) – A polynomial \(b(x)\) over \(\mathrm{GF}(q)\).

Returns

  • galois.Poly – Polynomial greatest common divisor of \(a(x)\) and \(b(x)\).

  • galois.Poly – Polynomial \(x(x)\), such that \(a x + b y = gcd(a, b)\).

  • galois.Poly – Polynomial \(y(x)\), such that \(a x + b y = gcd(a, b)\).

Examples

In [1]: GF = galois.GF(7)

In [2]: a = galois.Poly.Roots([2,2,2,3,6], field=GF); a
Out[2]: Poly(x^5 + 6x^4 + x + 3, GF(7))

# a(x) and b(x) only share the root 2 in common
In [3]: b = galois.Poly.Roots([1,2], field=GF); b
Out[3]: Poly(x^2 + 4x + 2, GF(7))

In [4]: gcd, x, y = galois.poly_gcd(a, b)

# The GCD has only 2 as a root with multiplicity 1
In [5]: gcd.roots(multiplicity=True)
Out[5]: (GF([2], order=7), array([1]))

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

Returns the nearest prime \(p\), such that \(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

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

  • list – List 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]: ([2, 3, 5], [3, 1, 1])

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

Prime factorization of 1 less than a large prime.

In [4]: prime =1000000000000000035000061

In [5]: galois.is_prime(prime)
Out[5]: True

In [6]: p, k = galois.prime_factors(prime - 1)

In [7]: p, k
Out[7]: ([2, 3, 5, 17, 19, 51599587203302375387], [2, 1, 1, 1, 1, 1])

In [8]: np.multiply.reduce(np.array(p) ** np.array(k))
Out[8]: 1000000000000000035000060
galois.primes(n)[source]

Returns the primes \(p \le n\).

Parameters

n (int) – A positive integer.

Returns

The primes up to and including \(n\).

Return type

list

Examples

In [1]: galois.primes(19)
Out[1]: [2, 3, 5, 7, 11, 13, 17, 19]
galois.primitive_root(n, start=1, stop=None, largest=False)[source]

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) for 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}\).

  • largest (bool, optional) – Return the largest primitive root in the specified range, not the smallest. 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 [1]: n = 6

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

# 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, 5}

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

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: {}, 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 [7]: n = 7

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

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

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

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

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

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

In [15]: galois.primitive_root(n, largest=True)
Out[15]: 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 [16]: n = 8

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

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

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

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

# Test all elements for being primitive roots. The powers of a primitive span the congruence classes mod n.
In [21]: 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 [22]: galois.carmichael(n)
Out[22]: 2
galois.primitive_roots(n, start=1, stop=None, reverse=False)[source]

A generator that 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) for 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

A generator of all the positive primitive \(n\)-th roots of unity, \(x\). Use list(galois.primitive_roots(n)) to retrieve them all instantly. Otherwise, you can access them in a for loop or list comprehension.

Return type

typing.Generator

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

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

# 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, 5}

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

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

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

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

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

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

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

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

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

In [15]: n = 1000000000000000035000061

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

# Only list some of the primitive roots
In [17]: list(galois.primitive_roots(n, stop=100))
Out[17]: [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 [18]: 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 [19]: n = 8

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

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

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

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

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

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

Parameters

n (int) – A positive integer.

Returns

The totatives of \(n\).

Return type

list

Examples

In [1]: n = 20

In [2]: totatives = galois.totatives(n); totatives
Out[2]: [1, 3, 7, 9, 11, 13, 17, 19]

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

In [4]: len(totatives) == phi
Out[4]: True