galois.GF2¶

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

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

This class is a subclass of galois.FieldArray and has metaclass galois.FieldMeta.

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.FieldMeta.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.

Examples

This class is equivalent (and, in fact, identical) to the class returned from the Galois field array class constructor.

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

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

In [208]: GF2 is galois.GF2
Out[208]: True

The Galois field properties can be viewed by class attributes, see galois.FieldMeta.

# View a summary of the field's properties
In [209]: print(galois.GF2.properties)
GF(2):
  structure: Finite Field
  characteristic: 2
  degree: 1
  order: 2

# Or access each attribute individually
In [210]: galois.GF2.irreducible_poly
Out[210]: Poly(x + 1, GF(2))

In [211]: galois.GF2.is_prime_field
Out[211]: True

The class’s constructor mimics the call signature of numpy.array().

# Construct a Galois field array from an iterable
In [212]: galois.GF2([1,0,1,1,0,0,0,1])
Out[212]: GF([1, 0, 1, 1, 0, 0, 0, 1], order=2)

# Or an iterable of iterables
In [213]: galois.GF2([[1,0],[1,1]])
Out[213]: 
GF([[1, 0],
    [1, 1]], order=2)

# Or a single integer
In [214]: galois.GF2(1)
Out[214]: GF(1, order=2)

Constructors

`Elements`([dtype])	Creates a Galois field array of the field’s elements \(\{0, \dots, p^m-1\}\).
`Identity`(size[, dtype])	Creates an \(n \times n\) Galois field identity matrix.
`Ones`(shape[, dtype])	Creates a Galois field array with all ones.
`Random`([shape, low, high, dtype])	Creates a Galois field array with random field elements.
`Range`(start, stop[, step, dtype])	Creates a Galois field array with a range of field elements.
`Vandermonde`(a, m, n[, dtype])	Creates a \(m \times n\) Vandermonde matrix of \(a \in \mathrm{GF}(p^m)\).
`Vector`(array[, dtype])	Creates a Galois field array over \(\mathrm{GF}(p^m)\) from length-\(m\) vectors over the prime subfield \(\mathrm{GF}(p)\).
`Zeros`(shape[, dtype])	Creates a Galois field array with all zeros.

Methods

`lu_decompose`()	Decomposes the input array into the product of lower and upper triangular matrices.
`lup_decompose`()	Decomposes the input array into the product of lower and upper triangular matrices using partial pivoting.
`row_reduce`([ncols])	Performs Gaussian elimination on the matrix to achieve reduced row echelon form.
`vector`([dtype])	Converts the Galois field array over \(\mathrm{GF}(p^m)\) to length-\(m\) vectors over the prime subfield \(\mathrm{GF}(p)\).

classmethod Elements(dtype=None)¶

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.FieldMeta.dtypes.
Returns: A Galois field array of all the field’s elements.
Return type: galois.FieldArray

Examples

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

In [216]: GF.Elements()
Out[216]: 
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)¶

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.FieldMeta.dtypes.

Returns

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

Return type

galois.FieldArray

Examples

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

In [218]: GF.Identity(4)
Out[218]: 
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.FieldMeta.dtypes.

Returns

A Galois field array of ones.

Return type

galois.FieldArray

Examples

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

In [220]: GF.Ones((2,5))
Out[220]: 
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.FieldMeta.dtypes.

Returns

A Galois field array of random field elements.

Return type

galois.FieldArray

Examples

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

In [222]: GF.Random((2,5))
Out[222]: 
GF([[ 6, 21, 24, 10, 30],
    [ 5, 24, 21, 30, 19]], 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.FieldMeta.dtypes.

Returns

A Galois field array of a range of field elements.

Return type

galois.FieldArray

Examples

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

In [224]: GF.Range(10,20)
Out[224]: 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.FieldArray) – 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.FieldMeta.dtypes.

Returns

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

Return type

galois.FieldArray

Examples

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

In [226]: a = GF.primitive_element

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

In [228]: 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.FieldMeta.dtypes.

Returns

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

Return type

galois.FieldArray

Examples

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

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

In [231]: a = GF.Vector(vec); a
Out[231]: GF([45, 58,  4], order=2^6)

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

In [233]: a.vector()
Out[233]: 
GF([[1, 0, 1, 1, 0, 1],
    [1, 1, 1, 0, 1, 0],
    [0, 0, 0, 1, 0, 0]], 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.FieldMeta.dtypes.

Returns

A Galois field array of zeros.

Return type

galois.FieldArray

Examples

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

In [235]: GF.Zeros((2,5))
Out[235]: 
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.FieldArray – The lower triangular matrix.
galois.FieldArray – The upper triangular matrix.

Examples

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

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

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

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

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

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

lup_decompose()¶

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

Returns

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

Examples

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

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

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

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

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

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

# P A = L U
In [248]: np.array_equal(P @ A, L @ U)
Out[248]: 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.FieldArray

Examples

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

In [250]: A = GF.Random((4,4)); A
Out[250]: 
GF([[20,  1,  8, 18],
    [ 4, 21, 23, 11],
    [17, 19, 23, 17],
    [30,  6, 28, 25]], order=31)

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

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

One column is a linear combination of another.

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

In [254]: A = GF.Random((4,4)); A
Out[254]: 
GF([[27,  5, 13, 25],
    [23,  9, 27,  0],
    [ 1, 27, 24, 13],
    [ 5, 10,  6,  2]], order=31)

In [255]: A[:,2] = A[:,1] * GF(17); A
Out[255]: 
GF([[27,  5, 23, 25],
    [23,  9, 29,  0],
    [ 1, 27, 25, 13],
    [ 5, 10, 15,  2]], order=31)

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

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

One row is a linear combination of another.

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

In [259]: A = GF.Random((4,4)); A
Out[259]: 
GF([[12, 17, 25, 29],
    [21, 17,  7, 23],
    [30, 16, 10, 23],
    [ 3, 13,  5, 25]], order=31)

In [260]: A[3,:] = A[2,:] * GF(8); A
Out[260]: 
GF([[12, 17, 25, 29],
    [21, 17,  7, 23],
    [30, 16, 10, 23],
    [23,  4, 18, 29]], order=31)

In [261]: A.row_reduce()
Out[261]: 
GF([[ 1,  0,  0, 30],
    [ 0,  1,  0,  6],
    [ 0,  0,  1,  5],
    [ 0,  0,  0,  0]], order=31)

In [262]: np.linalg.matrix_rank(A)
Out[262]: 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.FieldMeta.dtypes.
Returns: A Galois field array of length-\(m\) vectors over \(\mathrm{GF}(p)\).
Return type: galois.FieldArray

Examples

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

In [264]: a = GF.Random(3); a
Out[264]: GF([ 9, 34, 29], order=2^6)

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

In [266]: GF.Vector(vec)
Out[266]: GF([ 9, 34, 29], order=2^6)