galois ¶

Examples

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

In [2]: GF.Identity(4)
Out[2]: 
GF([[1, 0, 0, 0],
    [0, 1, 0, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 1]], order=31)

classmethod Ones(shape, dtype=None)¶

Creates 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 class, i.e. the first element in galois.GFMeta.dtypes.

Returns

A Galois field array of ones.

Return type

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)¶

Creates 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 class, i.e. the first element in galois.GFMeta.dtypes.

Returns

A Galois field array of random field elements.

Return type

Examples

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

In [2]: GF.Random((2,5))
Out[2]: 
GF([[ 2, 18,  3,  8, 23],
    [26, 25, 20, 30,  2]], order=31)

classmethod Range(start, stop, step=1, dtype=None)¶

Creates 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 class, i.e. the first element in galois.GFMeta.dtypes.

Returns

A Galois field array of a range of field elements.

Return type

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 Vandermonde(a, m, n, dtype=None)¶

Creates a \(m \times n\) Vandermonde matrix of \(a \in \mathrm{GF}(p^m)\).

Parameters

a (int, galois.GFArray) – An element of \(\mathrm{GF}(p^m)\).
m (int) – The number of rows in the Vandermonde matrix.
n (int) – The number of columns in the Vandermonde matrix.
dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest valid dtype for this class, i.e. the first element in galois.GFMeta.dtypes.

Returns

The \(m \times n\) Vandermonde matrix.

Return type

Examples

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

In [2]: a = GF.primitive_element

In [3]: V = GF.Vandermonde(a, 7, 7)

In [4]: with GF.display("power"):
   ...:     print(V)
   ...: 
GF([[1  , 1  , 1  , 1  , 1  , 1  , 1  ],
    [1  , α  , α^2, α^3, α^4, α^5, α^6],
    [1  , α^2, α^4, α^6, α  , α^3, α^5],
    [1  , α^3, α^6, α^2, α^5, α  , α^4],
    [1  , α^4, α  , α^5, α^2, α^6, α^3],
    [1  , α^5, α^3, α  , α^6, α^4, α^2],
    [1  , α^6, α^5, α^4, α^3, α^2, α  ]], order=2^3)

classmethod Vector(array, dtype=None)¶

Creates a Galois field array over \(\mathrm{GF}(p^m)\) from length-\(m\) vectors over the prime subfield \(\mathrm{GF}(p)\).

Parameters

array (array_like) – The input array with field elements in \(\mathrm{GF}(p)\) to be converted to a Galois field array in \(\mathrm{GF}(p^m)\). The last dimension of the input array must be \(m\). An input array with shape (n1, n2, m) has output shape (n1, n2).
dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest valid dtype for this class, i.e. the first element in galois.GFMeta.dtypes.

Returns

A Galois field array over \(\mathrm{GF}(p^m)\).

Return type

Examples

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

In [2]: vec = galois.GF2.Random((3,6)); vec
Out[2]: 
GF([[1, 0, 0, 1, 0, 1],
    [1, 1, 0, 1, 0, 1],
    [0, 0, 1, 0, 0, 1]], order=2)

In [3]: a = GF.Vector(vec); a
Out[3]: GF([37, 53,  9], order=2^6)

In [4]: with GF.display("poly"):
   ...:     print(a)
   ...: 
GF([α^5 + α^2 + 1, α^5 + α^4 + α^2 + 1, α^3 + 1], order=2^6)

In [5]: a.vector()
Out[5]: 
GF([[1, 0, 0, 1, 0, 1],
    [1, 1, 0, 1, 0, 1],
    [0, 0, 1, 0, 0, 1]], order=2)

classmethod Zeros(shape, dtype=None)¶

Creates 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 class, i.e. the first element in galois.GFMeta.dtypes.

Returns

A Galois field array of zeros.

Return type

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)

lu_decompose()¶

Decomposes the input array into the product of lower and upper triangular matrices.

Returns

galois.GFArray – The lower triangular matrix.
galois.GFArray – The upper triangular matrix.

Examples

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

# Not every square matrix has an LU decomposition
In [2]: A = GF([[2, 4, 4, 1], [3, 3, 1, 4], [4, 3, 4, 2], [4, 4, 3, 1]])

In [3]: L, U = A.lu_decompose()

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

In [5]: U
Out[5]: 
GF([[2, 4, 4, 1],
    [0, 2, 0, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 4]], order=5)

# A = L U
In [6]: np.array_equal(A, L @ U)
Out[6]: True

lup_decompose()¶

Decomposes the input array into the product of lower and upper triangular matrices using partial pivoting.

Returns

galois.GFArray – The lower triangular matrix.
galois.GFArray – The upper triangular matrix.
galois.GFArray – The permutation matrix.

Examples

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

In [2]: A = GF([[1, 3, 2, 0], [3, 4, 2, 3], [0, 2, 1, 4], [4, 3, 3, 1]])

In [3]: L, U, P = A.lup_decompose()

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

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

In [6]: P
Out[6]: 
GF([[1, 0, 0, 0],
    [0, 0, 1, 0],
    [0, 1, 0, 0],
    [0, 0, 0, 1]], order=5)

# P A = L U
In [7]: np.array_equal(P @ A, L @ U)
Out[7]: True

row_reduce(ncols=None)¶

Performs Gaussian elimination on the matrix to achieve reduced row echelon form.

Row reduction operations

Swap the position of any two rows.
Multiply a row by a non-zero scalar.
Add one row to a scalar multiple of another row.

Parameters: ncols (int, optional) – The number of columns to perform Gaussian elimination over. The default is None which represents the number of columns of the input array.
Returns: The reduced row echelon form of the input array.
Return type: galois.GFArray

Examples

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

In [2]: A = GF.Random((4,4)); A
Out[2]: 
GF([[ 3, 17, 21,  2],
    [14,  4, 11,  8],
    [11,  3, 19, 14],
    [ 6, 23, 30,  6]], order=31)

In [3]: A.row_reduce()
Out[3]: 
GF([[1, 0, 0, 0],
    [0, 1, 0, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 1]], order=31)

In [4]: np.linalg.matrix_rank(A)
Out[4]: 4

One column is a linear combination of another.

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

In [6]: A = GF.Random((4,4)); A
Out[6]: 
GF([[20, 24, 11,  4],
    [11, 23,  1, 16],
    [20, 16, 10, 19],
    [ 1,  1, 30, 28]], order=31)

In [7]: A[:,2] = A[:,1] * GF(17); A
Out[7]: 
GF([[20, 24,  5,  4],
    [11, 23, 19, 16],
    [20, 16, 24, 19],
    [ 1,  1, 17, 28]], order=31)

In [8]: A.row_reduce()
Out[8]: 
GF([[ 1,  0,  0,  0],
    [ 0,  1, 17,  0],
    [ 0,  0,  0,  1],
    [ 0,  0,  0,  0]], order=31)

In [9]: np.linalg.matrix_rank(A)
Out[9]: 3

One row is a linear combination of another.

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

In [11]: A = GF.Random((4,4)); A
Out[11]: 
GF([[30,  6, 25,  9],
    [17, 27, 21,  9],
    [24,  6, 12, 13],
    [ 2, 16, 30, 27]], order=31)

In [12]: A[3,:] = A[2,:] * GF(8); A
Out[12]: 
GF([[30,  6, 25,  9],
    [17, 27, 21,  9],
    [24,  6, 12, 13],
    [ 6, 17,  3, 11]], order=31)

In [13]: A.row_reduce()
Out[13]: 
GF([[ 1,  0,  0, 11],
    [ 0,  1,  0, 21],
    [ 0,  0,  1, 28],
    [ 0,  0,  0,  0]], order=31)

In [14]: np.linalg.matrix_rank(A)
Out[14]: 3

vector(dtype=None)¶

Converts the Galois field array over \(\mathrm{GF}(p^m)\) to length-\(m\) vectors over the prime subfield \(\mathrm{GF}(p)\).

For an input array with shape (n1, n2), the output shape is (n1, n2, m).

Parameters: dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest valid dtype for this class, i.e. the first element in galois.GFMeta.dtypes.
Returns: A Galois field array of length-\(m\) vectors over \(\mathrm{GF}(p)\).
Return type: galois.GFArray

Examples

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

In [2]: a = GF.Random(3); a
Out[2]: GF([24, 33, 48], order=2^6)

In [3]: vec = a.vector(); vec
Out[3]: 
GF([[0, 1, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 1],
    [1, 1, 0, 0, 0, 0]], order=2)

In [4]: GF.Vector(vec)
Out[4]: GF([24, 33, 48], order=2^6)

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

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([[1, 5, 6, 2, 4],
    [5, 2, 6, 3, 0]], 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 or tuple of int or str, int, or str.
dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest valid dtype for this class, i.e. the first element in galois.GFMeta.dtypes.
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 ({"K", "A", "C", "F"}, 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

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([ 26,  95,  80,  14,  28, 167,  62,  15, 194,  99], 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([118, 137,  62, 156,  60,  22, 199, 163, 207, 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]¶

Creates 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 class, i.e. the first element in galois.GFMeta.dtypes.
Returns: A Galois field array of all the field’s elements.
Return type: galois.GFArray

Examples

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

In [25]: GF.Elements()
Out[25]: 
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 Identity(size, dtype=None)[source]¶

Creates an \(n \times n\) Galois field identity matrix.

Parameters

size (int) – The size \(n\) along one axis of the matrix. The resulting array has shape (size,size).
dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest valid dtype for this class, i.e. the first element in galois.GFMeta.dtypes.

Returns

A Galois field identity matrix of shape (size, size).

Return type

Examples

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

In [27]: GF.Identity(4)
Out[27]: 
GF([[1, 0, 0, 0],
    [0, 1, 0, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 1]], order=31)

classmethod Ones(shape, dtype=None)[source]¶

Creates 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 class, i.e. the first element in galois.GFMeta.dtypes.

Returns

A Galois field array of ones.

Return type

Examples

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

In [29]: GF.Ones((2,5))
Out[29]: 
GF([[1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1]], order=31)

classmethod Random(shape=(), low=0, high=None, dtype=None)[source]¶

Creates 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 class, i.e. the first element in galois.GFMeta.dtypes.

Returns

A Galois field array of random field elements.

Return type

Examples

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

In [31]: GF.Random((2,5))
Out[31]: 
GF([[ 3, 18, 23, 24, 18],
    [20,  5,  1,  6, 26]], order=31)

classmethod Range(start, stop, step=1, dtype=None)[source]¶

Creates 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 class, i.e. the first element in galois.GFMeta.dtypes.

Returns

A Galois field array of a range of field elements.

Return type

Examples

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

In [33]: GF.Range(10,20)
Out[33]: GF([10, 11, 12, 13, 14, 15, 16, 17, 18, 19], order=31)

classmethod Vandermonde(a, m, n, dtype=None)[source]¶

Creates a \(m \times n\) Vandermonde matrix of \(a \in \mathrm{GF}(p^m)\).

Parameters

a (int, galois.GFArray) – An element of \(\mathrm{GF}(p^m)\).
m (int) – The number of rows in the Vandermonde matrix.
n (int) – The number of columns in the Vandermonde matrix.
dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest valid dtype for this class, i.e. the first element in galois.GFMeta.dtypes.

Returns

The \(m \times n\) Vandermonde matrix.

Return type

Examples

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

In [35]: a = GF.primitive_element

In [36]: V = GF.Vandermonde(a, 7, 7)

In [37]: with GF.display("power"):
   ....:     print(V)
   ....: 
GF([[1  , 1  , 1  , 1  , 1  , 1  , 1  ],
    [1  , α  , α^2, α^3, α^4, α^5, α^6],
    [1  , α^2, α^4, α^6, α  , α^3, α^5],
    [1  , α^3, α^6, α^2, α^5, α  , α^4],
    [1  , α^4, α  , α^5, α^2, α^6, α^3],
    [1  , α^5, α^3, α  , α^6, α^4, α^2],
    [1  , α^6, α^5, α^4, α^3, α^2, α  ]], order=2^3)

classmethod Vector(array, dtype=None)[source]¶

Creates a Galois field array over \(\mathrm{GF}(p^m)\) from length-\(m\) vectors over the prime subfield \(\mathrm{GF}(p)\).

Parameters

array (array_like) – The input array with field elements in \(\mathrm{GF}(p)\) to be converted to a Galois field array in \(\mathrm{GF}(p^m)\). The last dimension of the input array must be \(m\). An input array with shape (n1, n2, m) has output shape (n1, n2).
dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest valid dtype for this class, i.e. the first element in galois.GFMeta.dtypes.

Returns

A Galois field array over \(\mathrm{GF}(p^m)\).

Return type

Examples

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

In [39]: vec = galois.GF2.Random((3,6)); vec
Out[39]: 
GF([[1, 1, 0, 1, 1, 1],
    [0, 0, 1, 0, 0, 0],
    [1, 0, 0, 1, 1, 0]], order=2)

In [40]: a = GF.Vector(vec); a
Out[40]: GF([55,  8, 38], order=2^6)

In [41]: with GF.display("poly"):
   ....:     print(a)
   ....: 
GF([α^5 + α^4 + α^2 + α + 1, α^3, α^5 + α^2 + α], order=2^6)

In [42]: a.vector()
Out[42]: 
GF([[1, 1, 0, 1, 1, 1],
    [0, 0, 1, 0, 0, 0],
    [1, 0, 0, 1, 1, 0]], order=2)

classmethod Zeros(shape, dtype=None)[source]¶

Creates 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 class, i.e. the first element in galois.GFMeta.dtypes.

Returns

A Galois field array of zeros.

Return type

Examples

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

In [44]: GF.Zeros((2,5))
Out[44]: 
GF([[0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]], order=31)

lu_decompose()[source]¶

Decomposes the input array into the product of lower and upper triangular matrices.

Returns

galois.GFArray – The lower triangular matrix.
galois.GFArray – The upper triangular matrix.

Examples

In [45]: GF = galois.GF(5)

# Not every square matrix has an LU decomposition
In [46]: A = GF([[2, 4, 4, 1], [3, 3, 1, 4], [4, 3, 4, 2], [4, 4, 3, 1]])

In [47]: L, U = A.lu_decompose()

In [48]: L
Out[48]: 
GF([[1, 0, 0, 0],
    [4, 1, 0, 0],
    [2, 0, 1, 0],
    [2, 3, 0, 1]], order=5)

In [49]: U
Out[49]: 
GF([[2, 4, 4, 1],
    [0, 2, 0, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 4]], order=5)

# A = L U
In [50]: np.array_equal(A, L @ U)
Out[50]: True

lup_decompose()[source]¶

Decomposes the input array into the product of lower and upper triangular matrices using partial pivoting.

Returns

galois.GFArray – The lower triangular matrix.
galois.GFArray – The upper triangular matrix.
galois.GFArray – The permutation matrix.

Examples

In [51]: GF = galois.GF(5)

In [52]: A = GF([[1, 3, 2, 0], [3, 4, 2, 3], [0, 2, 1, 4], [4, 3, 3, 1]])

In [53]: L, U, P = A.lup_decompose()

In [54]: L
Out[54]: 
GF([[1, 0, 0, 0],
    [0, 1, 0, 0],
    [3, 0, 1, 0],
    [4, 3, 2, 1]], order=5)

In [55]: U
Out[55]: 
GF([[1, 3, 2, 0],
    [0, 2, 1, 4],
    [0, 0, 1, 3],
    [0, 0, 0, 3]], order=5)

In [56]: P
Out[56]: 
GF([[1, 0, 0, 0],
    [0, 0, 1, 0],
    [0, 1, 0, 0],
    [0, 0, 0, 1]], order=5)

# P A = L U
In [57]: np.array_equal(P @ A, L @ U)
Out[57]: True

row_reduce(ncols=None)[source]¶

Performs Gaussian elimination on the matrix to achieve reduced row echelon form.

Row reduction operations

Swap the position of any two rows.
Multiply a row by a non-zero scalar.
Add one row to a scalar multiple of another row.

Parameters: ncols (int, optional) – The number of columns to perform Gaussian elimination over. The default is None which represents the number of columns of the input array.
Returns: The reduced row echelon form of the input array.
Return type: galois.GFArray

Examples

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

In [59]: A = GF.Random((4,4)); A
Out[59]: 
GF([[16,  6, 27, 27],
    [27,  4, 23,  0],
    [23,  2,  5, 19],
    [ 3, 18, 13, 10]], order=31)

In [60]: A.row_reduce()
Out[60]: 
GF([[1, 0, 0, 0],
    [0, 1, 0, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 1]], order=31)

In [61]: np.linalg.matrix_rank(A)
Out[61]: 4

One column is a linear combination of another.

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

In [63]: A = GF.Random((4,4)); A
Out[63]: 
GF([[ 7,  4, 27, 28],
    [18,  7, 15, 12],
    [22, 29, 23, 26],
    [ 4,  5, 24,  6]], order=31)

In [64]: A[:,2] = A[:,1] * GF(17); A
Out[64]: 
GF([[ 7,  4,  6, 28],
    [18,  7, 26, 12],
    [22, 29, 28, 26],
    [ 4,  5, 23,  6]], order=31)

In [65]: A.row_reduce()
Out[65]: 
GF([[ 1,  0,  0,  0],
    [ 0,  1, 17,  0],
    [ 0,  0,  0,  1],
    [ 0,  0,  0,  0]], order=31)

In [66]: np.linalg.matrix_rank(A)
Out[66]: 3

One row is a linear combination of another.

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

In [68]: A = GF.Random((4,4)); A
Out[68]: 
GF([[14, 17, 28, 27],
    [ 8, 27, 30, 28],
    [30, 22,  1,  8],
    [21, 25,  9,  2]], order=31)

In [69]: A[3,:] = A[2,:] * GF(8); A
Out[69]: 
GF([[14, 17, 28, 27],
    [ 8, 27, 30, 28],
    [30, 22,  1,  8],
    [23, 21,  8,  2]], order=31)

In [70]: A.row_reduce()
Out[70]: 
GF([[ 1,  0,  0,  5],
    [ 0,  1,  0, 19],
    [ 0,  0,  1, 29],
    [ 0,  0,  0,  0]], order=31)

In [71]: np.linalg.matrix_rank(A)
Out[71]: 3

vector(dtype=None)[source]¶

Converts the Galois field array over \(\mathrm{GF}(p^m)\) to length-\(m\) vectors over the prime subfield \(\mathrm{GF}(p)\).

For an input array with shape (n1, n2), the output shape is (n1, n2, m).

Parameters: dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest valid dtype for this class, i.e. the first element in galois.GFMeta.dtypes.
Returns: A Galois field array of length-\(m\) vectors over \(\mathrm{GF}(p)\).
Return type: galois.GFArray

Examples

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

In [73]: a = GF.Random(3); a
Out[73]: GF([11, 37, 11], order=2^6)

In [74]: vec = a.vector(); vec
Out[74]: 
GF([[0, 0, 1, 0, 1, 1],
    [1, 0, 0, 1, 0, 1],
    [0, 0, 1, 0, 1, 1]], order=2)

In [75]: GF.Vector(vec)
Out[75]: GF([11, 37, 11], order=2^6)

class galois.GFMeta(name, bases, namespace, **kwargs)¶

Defines a metaclass for all galois.GFArray classes.

This metaclass gives galois.GFArray classes returned from galois.GF() class methods and properties relating to its Galois field.

compile(mode, target='cpu')¶

Recompile the just-in-time compiled numba ufuncs with a new calculation mode or target.

Parameters

mode (str) – The method of field computation, either "jit-lookup", "jit-calculate", "python-calculate". The “jit-lookup” mode will use Zech log, log, and anti-log lookup tables for speed. The “jit-calculate” mode will not store any lookup tables, but perform field arithmetic on the fly. The “jit-calculate” mode is designed for large fields that cannot store lookup tables in RAM. Generally, “jit-calculate” is slower than “jit-lookup”. The “python-calculate” mode is reserved for extremely large fields. In this mode the ufuncs are not JIT-compiled, but are pur python functions operating on python ints. The list of valid modes for this field is in galois.GFMeta.ufunc_modes.
target (str, optional) – The target keyword argument from numba.vectorize, either "cpu", "parallel", or "cuda". The default is "cpu". For extremely large fields the only supported target is "cpu" (which doesn’t use numba it uses pure python to calculate the field arithmetic). The list of valid targets for this field is in galois.GFMeta.ufunc_targets.

display(mode='int')[source]¶

Sets the display mode for all Galois field arrays of this type.

The display mode can be set to either the integer representation, polynomial representation, or power representation. This function updates display_mode.

For the power representation, np.log() is computed on each element. So for large fields without lookup tables, this may take longer than desired.

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

Examples

Change the display mode by calling the display() method.

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

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

# Change the display mode going forward
In [3]: GF.display("poly"); a
Out[3]: GF(α + 1, order=2^8)

In [4]: GF.display("power"); a
Out[4]: GF(α^25, order=2^8)

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

The display() method can also be used as a context manager, as shown below.

For the polynomial representation, when the primitive element is \(x \in \mathrm{GF}(p)[x]\) the polynomial indeterminate used is α.

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

In [7]: print(GF.properties)
GF(2^8):
  characteristic: 2
  degree: 8
  order: 256
  irreducible_poly: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))
  is_primitive_poly: True
  primitive_element: GF(2, order=2^8)

In [8]: a = GF.Random(); a
Out[8]: GF(254, order=2^8)

In [9]: with GF.display("poly"):
   ...:     print(a)
   ...: 
GF(α^7 + α^6 + α^5 + α^4 + α^3 + α^2 + α, order=2^8)

In [10]: with GF.display("power"):
   ....:     print(a)
   ....: 
GF(α^88, order=2^8)

But when the primitive element is not \(x \in \mathrm{GF}(p)[x]\), the polynomial indeterminate used is x.

In [11]: GF = galois.GF(2**8, irreducible_poly=galois.Poly.Degrees([8,4,3,1,0]))

In [12]: print(GF.properties)
GF(2^8):
  characteristic: 2
  degree: 8
  order: 256
  irreducible_poly: Poly(x^8 + x^4 + x^3 + x + 1, GF(2))
  is_primitive_poly: False
  primitive_element: GF(3, order=2^8)

In [13]: a = GF.Random(); a
Out[13]: GF(63, order=2^8)

In [14]: with GF.display("poly"):
   ....:     print(a)
   ....: 
GF(x^5 + x^4 + x^3 + x^2 + x + 1, order=2^8)

In [15]: with GF.display("power"):
   ....:     print(a)
   ....: 
GF(α^142, order=2^8)

property characteristic¶

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

Examples

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

In [2]: GF.characteristic
Out[2]: 2

In [3]: a = GF.Random(); a
Out[3]: GF(96, order=2^8)

In [4]: a * GF.characteristic
Out[4]: GF(0, order=2^8)

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

In [6]: GF.characteristic
Out[6]: 31

In [7]: a = GF.Random(); a
Out[7]: GF(28, order=31)

In [8]: a * GF.characteristic
Out[8]: GF(0, order=31)

Type: int

property default_ufunc_mode¶

The default ufunc arithmetic mode for this Galois field.

Examples

In [1]: galois.GF(2).default_ufunc_mode
Out[1]: 'jit-calculate'

In [2]: galois.GF(2**8).default_ufunc_mode
Out[2]: 'jit-lookup'

In [3]: galois.GF(31).default_ufunc_mode
Out[3]: 'jit-lookup'

In [4]: galois.GF(2**100).default_ufunc_mode
Out[4]: 'python-calculate'

Type: str

property degree¶

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

Examples

In [1]: galois.GF(2).degree
Out[1]: 1

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

In [3]: galois.GF(31).degree
Out[3]: 1

# galois.GF(7**5).degree

Type: int

property display_mode¶

The representation of Galois field elements, either "int", "poly", or "power". This can be changed with display().

Examples

For the polynomial representation, when the primitive element is \(x \in \mathrm{GF}(p)[x]\) the polynomial indeterminate used is α.

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

In [2]: print(GF.properties)
GF(2^8):
  characteristic: 2
  degree: 8
  order: 256
  irreducible_poly: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))
  is_primitive_poly: True
  primitive_element: GF(2, order=2^8)

In [3]: a = GF.Random(); a
Out[3]: GF(159, order=2^8)

In [4]: with GF.display("poly"):
   ...:     print(a)
   ...: 
GF(α^7 + α^4 + α^3 + α^2 + α + 1, order=2^8)

In [5]: with GF.display("power"):
   ...:     print(a)
   ...: 
GF(α^46, order=2^8)

But when the primitive element is not \(x \in \mathrm{GF}(p)[x]\), the polynomial indeterminate used is x.

In [6]: GF = galois.GF(2**8, irreducible_poly=galois.Poly.Degrees([8,4,3,1,0]))

In [7]: print(GF.properties)
GF(2^8):
  characteristic: 2
  degree: 8
  order: 256
  irreducible_poly: Poly(x^8 + x^4 + x^3 + x + 1, GF(2))
  is_primitive_poly: False
  primitive_element: GF(3, order=2^8)

In [8]: a = GF.Random(); a
Out[8]: GF(46, order=2^8)

In [9]: with GF.display("poly"):
   ...:     print(a)
   ...: 
GF(x^5 + x^3 + x^2 + x, order=2^8)

In [10]: with GF.display("power"):
   ....:     print(a)
   ....: 
GF(α^9, order=2^8)

Type: str

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

Examples

In [1]: galois.GF(2).dtypes
Out[1]: 
[numpy.uint8,
 numpy.uint16,
 numpy.uint32,
 numpy.int8,
 numpy.int16,
 numpy.int32,
 numpy.int64]

In [2]: galois.GF(2**8).dtypes
Out[2]: 
[numpy.uint8,
 numpy.uint16,
 numpy.uint32,
 numpy.int16,
 numpy.int32,
 numpy.int64]

In [3]: galois.GF(31).dtypes
Out[3]: 
[numpy.uint8,
 numpy.uint16,
 numpy.uint32,
 numpy.int8,
 numpy.int16,
 numpy.int32,
 numpy.int64]

# galois.GF(7**5).dtypes

For field’s with orders that cannot be represented by numpy.int64, the only valid dtype is numpy.object_.

In [4]: galois.GF(2**100).dtypes
Out[4]: [numpy.object_]

In [5]: galois.GF(36893488147419103183).dtypes
Out[5]: [numpy.object_]

Type: list

property irreducible_poly¶

The irreducible polynomial \(f(x)\) of the Galois field \(\mathrm{GF}(p^m)\). The irreducible polynomial is of degree \(m\) over \(\mathrm{GF}(p)\).

Examples

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

In [2]: galois.GF(2**8).irreducible_poly
Out[2]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))

In [3]: galois.GF(31).irreducible_poly
Out[3]: Poly(x + 28, GF(31))

# galois.GF(7**5).irreducible_poly

Type: galois.Poly

property is_extension_field¶

Indicates if the field’s order is a prime power.

Examples

In [1]: galois.GF(2).is_extension_field
Out[1]: False

In [2]: galois.GF(2**8).is_extension_field
Out[2]: True

In [3]: galois.GF(31).is_extension_field
Out[3]: False

# galois.GF(7**5).is_extension_field

Type: bool

property is_prime_field¶

Indicates if the field’s order is prime.

Examples

In [1]: galois.GF(2).is_prime_field
Out[1]: True

In [2]: galois.GF(2**8).is_prime_field
Out[2]: False

In [3]: galois.GF(31).is_prime_field
Out[3]: True

# galois.GF(7**5).is_prime_field

Type: bool

property is_primitive_poly¶

Indicates whether the irreducible_poly is a primitive polynomial.

Examples

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

In [2]: GF.irreducible_poly
Out[2]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))

In [3]: GF.primitive_element
Out[3]: GF(2, order=2^8)

# The irreducible polynomial is a primitive polynomial is the primitive element is a root
In [4]: GF.irreducible_poly(GF.primitive_element, field=GF)
Out[4]: GF(0, order=2^8)

In [5]: GF.is_primitive_poly
Out[5]: True

# Field used in AES
In [6]: GF = galois.GF(2**8, irreducible_poly=galois.Poly.Degrees([8,4,3,1,0]))

In [7]: GF.irreducible_poly
Out[7]: Poly(x^8 + x^4 + x^3 + x + 1, GF(2))

In [8]: GF.primitive_element
Out[8]: GF(3, order=2^8)

# The irreducible polynomial is a primitive polynomial is the primitive element is a root
In [9]: GF.irreducible_poly(GF.primitive_element, field=GF)
Out[9]: GF(6, order=2^8)

In [10]: GF.is_primitive_poly
Out[10]: False

Type: bool

property name¶

The Galois field name.

Examples

In [1]: galois.GF(2).name
Out[1]: 'GF(2)'

In [2]: galois.GF(2**8).name
Out[2]: 'GF(2^8)'

In [3]: galois.GF(31).name
Out[3]: 'GF(31)'

# galois.GF(7**5).name

Type: str

property order¶

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.

Examples

In [1]: galois.GF(2).order
Out[1]: 2

In [2]: galois.GF(2**8).order
Out[2]: 256

In [3]: galois.GF(31).order
Out[3]: 31

# galois.GF(7**5).order

Type: int

property prime_subfield¶

The prime subfield \(\mathrm{GF}(p)\) of the extension field \(\mathrm{GF}(p^m)\).

Examples

In [1]: print(galois.GF(2).prime_subfield.properties)
GF(2):
  characteristic: 2
  degree: 1
  order: 2
  irreducible_poly: Poly(x + 1, GF(2))
  is_primitive_poly: True
  primitive_element: GF(1, order=2)

In [2]: print(galois.GF(2**8).prime_subfield.properties)
GF(2):
  characteristic: 2
  degree: 1
  order: 2
  irreducible_poly: Poly(x + 1, GF(2))
  is_primitive_poly: True
  primitive_element: GF(1, order=2)

In [3]: print(galois.GF(31).prime_subfield.properties)
GF(31):
  characteristic: 31
  degree: 1
  order: 31
  irreducible_poly: Poly(x + 28, GF(31))
  is_primitive_poly: True
  primitive_element: GF(3, order=31)

# print(galois.GF(7**5).prime_subfield.properties)

Type: galois.GFMeta

property primitive_element¶

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

A primitive element is a root of the primitive polynomial \(\f(x)\), such that \(f(\alpha) = 0\) over \(\mathrm{GF}(p^m)\).

Examples

In [1]: galois.GF(2).primitive_element
Out[1]: GF(1, order=2)

In [2]: galois.GF(2**8).primitive_element
Out[2]: GF(2, order=2^8)

In [3]: galois.GF(31).primitive_element
Out[3]: GF(3, order=31)

# galois.GF(7**5).primitive_element

Type: int

property primitive_elements¶

All primitive elements \(\alpha\) of the Galois field \(\mathrm{GF}(p^m)\). A primitive element is a multiplicative generator of the field, such that \(\mathrm{GF}(p^m) = \{0, 1, \alpha^1, \alpha^2, \dots, \alpha^{p^m - 2}\}\).

Examples

In [1]: galois.GF(2).primitive_elements
Out[1]: GF([1], order=2)

In [2]: galois.GF(2**8).primitive_elements
Out[2]: 
GF([  2,   4,   6,   9,  13,  14,  16,  18,  19,  20,  22,  24,  25,  27,
     29,  30,  31,  34,  35,  40,  42,  43,  48,  49,  50,  52,  57,  60,
     63,  65,  66,  67,  71,  72,  73,  74,  75,  76,  81,  82,  83,  84,
     88,  90,  91,  92,  93,  95,  98,  99, 104, 105, 109, 111, 112, 113,
    118, 119, 121, 122, 123, 126, 128, 129, 131, 133, 135, 136, 137, 140,
    141, 142, 144, 148, 149, 151, 154, 155, 157, 158, 159, 162, 163, 164,
    165, 170, 171, 175, 176, 177, 178, 183, 187, 188, 189, 192, 194, 198,
    199, 200, 201, 202, 203, 204, 209, 210, 211, 212, 213, 216, 218, 222,
    224, 225, 227, 229, 232, 234, 236, 238, 240, 243, 246, 247, 248, 249,
    250, 254], order=2^8)

In [3]: galois.GF(31).primitive_elements
Out[3]: GF([ 3, 11, 12, 13, 17, 21, 22, 24], order=31)

# galois.GF(7**5).primitive_elements

Type: int

property properties¶

A formmatted string displaying relevant properties of the Galois field.

Examples

In [1]: print(galois.GF(2).properties)
GF(2):
  characteristic: 2
  degree: 1
  order: 2
  irreducible_poly: Poly(x + 1, GF(2))
  is_primitive_poly: True
  primitive_element: GF(1, order=2)

In [2]: print(galois.GF(2**8).properties)
GF(2^8):
  characteristic: 2
  degree: 8
  order: 256
  irreducible_poly: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))
  is_primitive_poly: True
  primitive_element: GF(2, order=2^8)

In [3]: print(galois.GF(31).properties)
GF(31):
  characteristic: 31
  degree: 1
  order: 31
  irreducible_poly: Poly(x + 28, GF(31))
  is_primitive_poly: True
  primitive_element: GF(3, order=31)

# print(galois.GF(7**5).properties)

Type: str

property ufunc_mode¶

The mode for ufunc compilation, either "jit-lookup", "jit-calculate", "python-calculate".

Examples

In [1]: galois.GF(2).ufunc_mode
Out[1]: 'jit-calculate'

In [2]: galois.GF(2**8).ufunc_mode
Out[2]: 'jit-lookup'

In [3]: galois.GF(31).ufunc_mode
Out[3]: 'jit-lookup'

# galois.GF(7**5).ufunc_mode

Type: str

property ufunc_modes¶

All supported ufunc modes for this Galois field array class.

Examples

In [1]: galois.GF(2).ufunc_modes
Out[1]: ['jit-calculate']

In [2]: galois.GF(2**8).ufunc_modes
Out[2]: ['jit-lookup', 'jit-calculate']

In [3]: galois.GF(31).ufunc_modes
Out[3]: ['jit-lookup', 'jit-calculate']

In [4]: galois.GF(2**100).ufunc_modes
Out[4]: ['python-calculate']

Type: list

property ufunc_target¶

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

Examples

In [1]: galois.GF(2).ufunc_target
Out[1]: 'cpu'

In [2]: galois.GF(2**8).ufunc_target
Out[2]: 'cpu'

In [3]: galois.GF(31).ufunc_target
Out[3]: 'cpu'

# galois.GF(7**5).ufunc_target

Type: str

property ufunc_targets¶

All supported ufunc targets for this Galois field array class.

Examples

In [1]: galois.GF(2).ufunc_targets
Out[1]: ['cpu', 'parallel', 'cuda']

In [2]: galois.GF(2**8).ufunc_targets
Out[2]: ['cpu', 'parallel', 'cuda']

In [3]: galois.GF(31).ufunc_targets
Out[3]: ['cpu', 'parallel', 'cuda']

In [4]: galois.GF(2**100).ufunc_targets
Out[4]: ['cpu']

Type: list

class galois.Poly(coeffs, field=None, order='desc')¶

Create a polynomial \(f(x)\) over \(\mathrm{GF}(p^m)\).

The polynomial \(f(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}(p^m)\).

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}(p^m)\) 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 \(f(x)\).

Return type

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 Degrees(degrees, coeffs=None, field=None)[source]¶

Constructs a polynomial over \(\mathrm{GF}(p^m)\) 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}(p^m)\) the polynomial is over. The default is`None` which represents galois.GF2.

Returns

The polynomial \(f(x)\).

Return type

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 'numpy.ndarray over GF(2)'>)[source]¶

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

Parameters: field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is galois.GF2.
Returns: The polynomial \(f(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 'numpy.ndarray over GF(2)'>)[source]¶

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

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

Parameters

integer (int) – The integer representation of the polynomial \(f(x)\).
field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is galois.GF2.

Returns

The polynomial \(f(x)\).

Return type

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 'numpy.ndarray over GF(2)'>)[source]¶

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

Parameters: field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is galois.GF2.
Returns: The polynomial \(f(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 'numpy.ndarray over GF(2)'>)[source]¶

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

Parameters

degree (int) – The degree of the polynomial.
field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is galois.GF2.

Returns

The polynomial \(f(x)\).

Return type

Examples

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

In [1]: galois.Poly.Random(5)
Out[1]: Poly(x^5 + x^4, 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(114x^5 + 210x^4 + 153x^3 + 69x^2 + 105x + 45, GF(2^8))

classmethod Roots(roots, multiplicities=None, field=None)[source]¶

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

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

\[ \begin{align}\begin{aligned}f(x) &= (x - r_0) (x - r_1) \dots (x - r_{d-1})\\f(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}(p^m)\) 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}(p^m)\) the polynomial is over. The default is`None` which represents galois.GF2.

Returns

The polynomial \(f(x)\).

Return type

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 'numpy.ndarray over GF(2)'>)[source]¶

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

Parameters: field (galois.GFArray, optional) – The field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is galois.GF2.
Returns: The polynomial \(f(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} f(x)\) of the polynomial \(f(x)\).

For the polynomial

\[f(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 \(f(x)\).
Return type: galois.Poly

References

https://en.wikipedia.org/wiki/Formal_derivative

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^4 + x + 1, GF(2))

In [2]: p.derivative()
Out[2]: Poly(x^6 + 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(x^11 + x^10 + 6x^9 + 2x^8 + 6x^7 + 4x^6 + 4x^5 + x^4 + 6x^3 + x^2 + x + 5, GF(7))

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

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

In [8]: p.derivative(3)
Out[8]: Poly(3x^8 + 6x^7 + 4x^3 + 2x^2 + 3x + 1, 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(41x^7 + 17x^6 + 138x^5 + 109x^4 + 175x^3 + 184x^2 + 115x + 121, GF(2^8))

In [12]: p.derivative()
Out[12]: Poly(41x^6 + 138x^4 + 175x^2 + 115, 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 \(f(x)\), such that \(f(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

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

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

\[f(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}(p^m) = \{0, 1, \alpha, \alpha^2, \dots, \alpha^{p^m-2}\}\), where \(\alpha\) is a primitive element of \(\mathrm{GF}(p^m)\).

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

\[a_0 = 0\]

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

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

The remaining elements of \(\mathrm{GF}(p^m)\) are powers of \(\alpha\). The following equations calculate \(p(\alpha^i)\), where \(\alpha^i\) is a root of \(f(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 \(f(x)\).
np.ndarray – The multiplicity of each root. Only returned if multiplicity=True.

References

https://en.wikipedia.org/wiki/Chien_search

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 array class to which the coefficients belong.

Examples

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

In [2]: a.field
Out[2]: <class 'numpy.ndarray over GF(2)'>

In [3]: b = galois.Poly.Random(5, field=galois.GF(2**8)); b
Out[3]: Poly(31x^5 + 196x^4 + 133x^3 + 41x^2 + 228x + 211, GF(2^8))

In [4]: b.field
Out[4]: <class 'numpy.ndarray over GF(2^8)'>

Type: galois.GFMeta

property integer¶

The integer representation of the polynomial. For polynomial \(f(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\) with elements in \(a_k \in \mathrm{GF}(p^m)\), the integer representation is \(i = a_{d} (p^m)^{d} + a_{d-1} (p^m)^{d-1} + \dots + a_1 (p^m) + 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, irreducible_poly=None, primitive_element=None, verify_irreducible=True, verify_primitive=True, mode='auto', target='cpu')¶

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

The created class will be a subclass of galois.GFArray with metaclass galois.GFMeta. The galois.GFArray inheritance provides the numpy.ndarray functionality. The galois.GFMeta metaclass provides a variety of class attributes and methods relating to the finite field.

Parameters

order (int) – The order \(p^m\) of the field \(\mathrm{GF}(p^m)\). The order must be a prime power.
irreducible_poly (int, galois.Poly, optional) – Optionally specify an irreducible polynomial of degree \(m\) over \(\mathrm{GF}(p)\) that will define the Galois field arithmetic. An integer may be provided, which is the integer representation of the irreducible polynomial. Default is None which uses the Conway polynomial \(C_{p,m}\) obtained from galois.conway_poly().
primitive_element (int, galois.Poly, optional) – Optionally specify a primitive element of the field \(\mathrm{GF}(p^m)\). A primitive element is a generator of the multiplicative group of the field. For prime fields \(\mathrm{GF}(p)\), the primitive element must be an integer and is a primitive root modulo \(p\). For extension fields \(\mathrm{GF}(p^m)\), the primitive element is a polynomial of degree less than \(m\) over \(\mathrm{GF}(p)\) or its integer representation. The default is None which uses galois.primitive_root(p) for prime fields and galois.primitive_element(irreducible_poly) for extension fields.
verify_irreducible (bool, optional) – Indicates whether to verify that the specified irreducible polynomial is in fact irreducible. The default is True. For large irreducible polynomials that are already known to be irreducible (and may take a long time to verify), this argument can be set to False.
verify_primitive (bool, optional) – Indicates whether to verify that the specified primitive element is in fact a generator of the multiplicative group. The default is True.
mode (str, optional) – The type of field computation, either "auto", "jit-lookup", or "jit-calculate". The default is "auto". The “jit-lookup” mode will use Zech log, log, and anti-log lookup tables for efficient calculation. The “jit-calculate” mode will not store any lookup tables, but instead perform field arithmetic on the fly. The “jit-calculate” mode is designed for large fields that cannot or should not store lookup tables in RAM. Generally, “jit-calculate” mode will be slower than “jit-lookup”. The “auto” mode will determine whether to use “jit-lookup” or “jit-calculate” based on the field’s size. In “auto” mode, field’s with order <= 2**16 will use the “jit-lookup” mode.
target (str, optional) – The target keyword argument from numba.vectorize(), either "cpu", "parallel", or "cuda".

Returns

A new Galois field array class that is a subclass of galois.GFArray with galois.GFMeta metaclass.

Return type

galois.GFMeta

Examples

Construct a Galois field array class with default irreducible polynomial and primitive element.

# Construct a GF(2^m) class
In [1]: GF256 = galois.GF(2**8)

# Notice the irreducible polynomial is primitive
In [2]: print(GF256.properties)
GF(2^8):
  characteristic: 2
  degree: 8
  order: 256
  irreducible_poly: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))
  is_primitive_poly: True
  primitive_element: GF(2, order=2^8)

In [3]: poly = GF256.irreducible_poly

Construct a Galois field specifying a specific irreducible polynomial.

# Field used in AES
In [4]: GF256_AES = galois.GF(2**8, irreducible_poly=galois.Poly.Degrees([8,4,3,1,0]))

In [5]: print(GF256_AES.properties)
GF(2^8):
  characteristic: 2
  degree: 8
  order: 256
  irreducible_poly: Poly(x^8 + x^4 + x^3 + x + 1, GF(2))
  is_primitive_poly: False
  primitive_element: GF(3, order=2^8)

# Construct a GF(p) class
In [6]: GF571 = galois.GF(571); print(GF571.properties)
GF(571):
  characteristic: 571
  degree: 1
  order: 571
  irreducible_poly: Poly(x + 568, GF(571))
  is_primitive_poly: True
  primitive_element: GF(3, order=571)

# Construct a very large GF(2^m) class
In [7]: GF2m = galois.GF(2**100); print(GF2m.properties)
GF(2^100):
  characteristic: 2
  degree: 100
  order: 1267650600228229401496703205376
  irreducible_poly: 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))
  is_primitive_poly: True
  primitive_element: GF(2, order=2^100)

# Construct a very large GF(p) class
In [8]: GFp = galois.GF(36893488147419103183); print(GFp.properties)
GF(36893488147419103183):
  characteristic: 36893488147419103183
  degree: 1
  order: 36893488147419103183
  irreducible_poly: Poly(x + 36893488147419103180, GF(36893488147419103183))
  is_primitive_poly: True
  primitive_element: GF(3, order=36893488147419103183)

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

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

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

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

A Conway polynomial is a an irreducible and primitive 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

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 previously been created, it will be created in this function since it’s needed for the construction of 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.crt(a, m)¶

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

This function implements the Chinese Remainder Theorem.

\[ \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.crt(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.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\).

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.fermat_primality_test(n)¶

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

References

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)¶

Finds the integer multiplicands of \(a\) and \(b\) such that \(a x + b y = \mathrm{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 = \mathrm{gcd}(a, b)\).
int – Integer \(y\), such that \(a x + b y = \mathrm{gcd}(a, b)\).

References

1. Moon, “Error Correction Coding”, Section 5.2.2: The Euclidean Algorithm and Euclidean Domains, p. 181
https://en.wikipedia.org/wiki/Euclidean_algorithm#Extended_Euclidean_algorithm

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)¶

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

https://en.wikipedia.org/wiki/Primitive_root_modulo_n

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

In [7]: roots = 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 = 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)¶

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

A polynomial \(f(x) \in \mathrm{GF}(p)[x]\) is reducible over \(\mathrm{GF}(p)\) if it can be represented as \(f(x) = g(x) h(x)\) for some \(g(x), h(x) \in \mathrm{GF}(p)[x]\) of strictly lower degree. If \(f(x)\) is not reducible, it is said to be irreducible. Since Galois fields are not algebraically closed, such irreducible polynomials exist.

This function implements 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

1. 1. Rabin. Probabilistic algorithms in finite fields. SIAM Journal on Computing (1980), 273–280. https://apps.dtic.mil/sti/pdfs/ADA078416.pdf
1. Gao and D. Panarino. Tests and constructions of irreducible polynomials over finite fields. https://www.math.clemson.edu/~sgao/papers/GP97a.pdf
https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields

Examples

# Conway polynomials are always irreducible (and primitive)
In [1]: f = galois.conway_poly(2, 5); f
Out[1]: Poly(x^5 + x^2 + 1, GF(2))

# f(x) has no roots in GF(2), a requirement of being irreducible
In [2]: f.roots()
Out[2]: GF([], order=2)

In [3]: galois.is_irreducible(f)
Out[3]: True

In [4]: g = galois.conway_poly(2, 4); g
Out[4]: Poly(x^4 + x + 1, GF(2))

In [5]: h = galois.conway_poly(2, 5); h
Out[5]: Poly(x^5 + x^2 + 1, GF(2))

In [6]: f = g * h; f
Out[6]: Poly(x^9 + x^5 + x^4 + x^3 + x^2 + x + 1, GF(2))

# Even though f(x) has no roots in GF(2), it is still reducible
In [7]: f.roots()
Out[7]: GF([], order=2)

In [8]: galois.is_irreducible(f)
Out[8]: False

galois.is_monic(poly)¶

Determines whether the polynomial is monic, i.e. having leading coefficient equal to 1.

Parameters: poly (galois.Poly) – A polynomial over a Galois field.
Returns: True if the polynomial is monic.
Return type: bool

Examples

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

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

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

In [4]: p = galois.Poly([3,0,4,5], field=GF); p
Out[4]: Poly(3x^3 + 4x + 5, GF(7))

In [5]: galois.is_monic(p)
Out[5]: False

galois.is_prime(n)¶

Determines if \(n\) is prime.

This algorithm will first run Fermat’s primality test to check \(n\) for compositeness, see galois.fermat_primality_test. 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 the algorithm will run seven rounds of Miller-Rabin’s primality test, see galois.miller_rabin_primality_test. With this many rounds, a result of True should have high probability of \(n\) 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(poly)¶

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

A degree-\(n\) polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is primitive if \(f(x)\ |\ (x^k - 1)\) for \(k = p^n - 1\) and no \(k\) less than \(p^n - 1\).

Parameters: poly (galois.Poly) – A polynomial \(f(x)\) over \(\mathrm{GF}(p)\).
Returns: True if the polynomial is primitive.
Return type: bool

Examples

All Conway polynomials are primitive.

In [1]: f = galois.conway_poly(2, 8); f
Out[1]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))

In [2]: galois.is_primitive(f)
Out[2]: True

In [3]: f = galois.conway_poly(3, 5); f
Out[3]: Poly(x^5 + 2x + 1, GF(3))

In [4]: galois.is_primitive(f)
Out[4]: True

The irreducible polynomial of \(\mathrm{GF}(2^8)\) for AES is not primitive.

In [5]: f = galois.Poly.Degrees([8,4,3,1,0]); f
Out[5]: Poly(x^8 + x^4 + x^3 + x + 1, GF(2))

In [6]: galois.is_primitive(f)
Out[6]: False

galois.is_primitive_element(element, irreducible_poly)¶

Determines if \(g(x)\) is a primitive element of the Galois field \(\mathrm{GF}(p^m)\) with degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(p)\).

The number of primitive elements of \(\mathrm{GF}(p^m)\) is \(\phi(p^m - 1)\), where \(\phi(n)\) is the Euler totient function, see galois.euler_totient.

Parameters

element (galois.Poly) – An element \(g(x)\) of \(\mathrm{GF}(p^m)\) as a polynomial over \(\mathrm{GF}(p)\) with degree less than \(m\).
irreducible_poly (galois.Poly) – The degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(p)\) that defines the extension field \(\mathrm{GF}(p^m)\).

Returns

True if \(g(x)\) is a primitive element of \(\mathrm{GF}(p^m)\) with irreducible polynomial \(f(x)\).

Return type

Examples

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

In [2]: f = galois.Poly([1,1,2], field=GF); f
Out[2]: Poly(x^2 + x + 2, GF(3))

In [3]: galois.is_irreducible(f)
Out[3]: True

In [4]: galois.is_primitive(f)
Out[4]: True

In [5]: g = galois.Poly.Identity(GF); g
Out[5]: Poly(x, GF(3))

In [6]: galois.is_primitive_element(g, f)
Out[6]: True

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

In [8]: f = galois.Poly([1,0,1], field=GF); f
Out[8]: Poly(x^2 + 1, GF(3))

In [9]: galois.is_irreducible(f)
Out[9]: True

In [10]: galois.is_primitive(f)
Out[10]: False

In [11]: g = galois.Poly.Identity(GF); g
Out[11]: Poly(x, GF(3))

In [12]: galois.is_primitive_element(g, f)
Out[12]: False

galois.is_primitive_root(g, n)¶

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

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]: galois.primitive_roots(7)
Out[3]: [3, 5]

galois.is_smooth(n, B)¶

Determines if the positive integer \(n\) is \(B\)-smooth, i.e. all its prime factors satisfy \(p \le B\).

The \(2\)-smooth numbers are the powers of \(2\). The \(5\)-smooth numbers are known as regular numbers. The \(7\)-smooth numbers are known as humble numbers or highly composite numbers.

Parameters

n (int) – A positive integer.
B (int) – The smoothness bound.

Returns

True if \(n\) is \(B\)-smooth.

Return type

Examples

In [1]: galois.is_smooth(2**10, 2)
Out[1]: True

In [2]: galois.is_smooth(10, 5)
Out[2]: True

In [3]: galois.is_smooth(12, 5)
Out[3]: True

In [4]: galois.is_smooth(60**2, 5)
Out[4]: True

galois.isqrt(n)¶

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

Note

This function is included for Python versions before 3.8. For Python 3.8 and later, this function calls math.isqrt() from the standard library.

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)¶

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.lcm(*integers)¶

Computes the least common multiple of the integer arguments.

Note

This function is included for Python versions before 3.9. For Python 3.9 and later, this function calls math.lcm() from the standard library.

Returns: The least common multiple of the integer arguments. If any argument is 0, the LCM is 0. If no arguments are provided, 1 is returned.
Return type: int

Examples

In [1]: galois.lcm()
Out[1]: 1

In [2]: galois.lcm(2, 4, 14)
Out[2]: 28

In [3]: galois.lcm(3, 0, 9)
Out[3]: 0

This function also works on arbitrarily-large integers.

In [4]: prime1, prime2 = galois.mersenne_primes(100)[-2:]

In [5]: prime1, prime2
Out[5]: (2305843009213693951, 618970019642690137449562111)

In [6]: lcm = galois.lcm(prime1, prime2); lcm
Out[6]: 1427247692705959880439315947500961989719490561

In [7]: lcm == prime1 * prime2
Out[7]: True

galois.mersenne_exponents(n=None)¶

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

https://oeis.org/A000043

Examples

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

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

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

galois.mersenne_primes(n=None)¶

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

https://oeis.org/A000668

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)¶

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

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)¶

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)¶

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

Examples

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

In [2]: f = galois.Poly.Random(10, field=GF); f
Out[2]: Poly(7x^10 + 20x^9 + 22x^8 + 25x^7 + 7x^6 + 10x^5 + 17x^4 + 10x^3 + 14x^2 + 3x + 4, GF(31))

In [3]: g = galois.Poly.Random(7, field=GF); g
Out[3]: Poly(5x^7 + 8x^6 + 12x^5 + 13x^3 + 23x^2 + 16x + 17, 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 + 19x^5 + 14x^4 + 2x^3 + 20x^2 + 19x + 18, 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 + 19x^5 + 14x^4 + 2x^3 + 20x^2 + 19x + 18, GF(31))

galois.poly_gcd(a, b)¶

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)¶

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(n)¶

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

The integer \(n\) can be factored into \(n = p_1^{e_1} p_2^{e_2} \dots p_{k-1}^{e_{k-1}}\).

Steps:

Test if \(n\) is prime. If so, return [n], [1].
Use trial division with a list of primes up to \(10^6\). If no residual factors, return the discovered prime factors.
Use Pollard’s Rho algorithm to find a non-trivial factor of the residual. Continue until all are found.

Parameters

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

Returns

list – Sorted list of \(k\) prime factors \(p = [p_1, p_2, \dots, p_{k-1}]\) with \(p_1 < p_2 < \dots < p_{k-1}\).
list – List of corresponding prime powers \(e = [e_1, e_2, \dots, e_{k-1}]\).

Examples

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

In [2]: p, e
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(e))
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, e = galois.prime_factors(prime - 1)

In [7]: p, e
Out[7]: ([2, 3, 5, 17, 19, 112850813, 457237177399], [2, 1, 1, 1, 1, 1, 1])

In [8]: np.multiply.reduce(np.array(p) ** np.array(e))
Out[8]: 2003764205241896700

galois.primes(n)¶

Returns all primes \(p\) for \(p \le n\).

Parameters: n (int) – A positive integer.
Returns: The primes up to and including \(n\).
Return type: list

References

https://oeis.org/A000040

Examples

In [1]: galois.primes(19)
Out[1]: [2, 3, 5, 7, 11, 13, 17, 19]

galois.primitive_element(irreducible_poly, start=None, stop=None, reverse=False)¶

Finds the smallest primitive element \(g(x)\) of the Galois field \(\mathrm{GF}(p^m)\) with degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(p)\).

Parameters

irreducible_poly (galois.Poly) – The degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(p)\) that defines the extension field \(\mathrm{GF}(p^m)\).
start (int, optional) – Starting value (inclusive, integer representation of the polynomial) in the search for a primitive element \(g(x)\) of \(\mathrm{GF}(p^m)\). The default is None which represents \(p\), which corresponds to \(g(x) = x\) over \(\mathrm{GF}(p)\).
stop (int, optional) – Stopping value (exclusive, integer representation of the polynomial) in the search for a primitive element \(g(x)\) of \(\mathrm{GF}(p^m)\). The default is None which represents \(p^m\), which corresponds to \(g(x) = x^m\) over \(\mathrm{GF}(p)\).
reverse (bool, optional) – Search for a primitive element in reverse order, i.e. find the largest primitive element first. Default is False.

Returns

A primitive element of \(\mathrm{GF}(p^m)\) with irreducible polynomial \(f(x)\). The primitive element \(g(x)\) is a polynomial over \(\mathrm{GF}(p)\) with degree less than \(m\).

Return type