galois.FieldArray

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

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

The galois.FieldArray 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.FieldArray 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 [5]: GF7 = galois.GF(7)

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

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

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

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

galois.FieldArray is a subclass of numpy.ndarray. The galois.FieldArray constructor has the same syntax as numpy.array(). The returned galois.FieldArray 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.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.

Returns

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

Return type

galois.FieldArray

Examples

Construct various kinds of Galois fields using galois.GF.

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

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

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

# Construct a very large GF(p) class
In [12]: 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 [13]: GF256.dtypes
Out[13]: 
[numpy.uint8,
 numpy.uint16,
 numpy.uint32,
 numpy.int16,
 numpy.int32,
 numpy.int64]

In [14]: GF571.dtypes
Out[14]: [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 [15]: GF2m.dtypes
Out[15]: [numpy.object_]

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

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

In [17]: a = GF256.Random(10); a
Out[17]: GF([ 63, 189, 255,   0, 135,  39, 226, 176, 102, 212], order=2^8)

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

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

In [19]: a = GF256.Random(10, dtype=np.uint32); a
Out[19]: GF([142, 141,  98, 209,  17,  34, 148, 208, 228,  81], order=2^8)

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

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

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

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

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

In [24]: GF256(l)
Out[24]: 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 [25]: a = x_np.view(GF256); a
Out[25]: GF([142,  27,  92, 253, 103], order=2^8)

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

In [27]: a
Out[27]: GF([  0,  27,  92, 253, 103], order=2^8)

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

Returns

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

Return type

galois.FieldArray

Examples

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

In [29]: GF.Elements()
Out[29]: 
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.FieldMeta.dtypes.

Returns

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

Return type

galois.FieldArray

Examples

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

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

Returns

A Galois field array of ones.

Return type

galois.FieldArray

Examples

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

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

Returns

A Galois field array of random field elements.

Return type

galois.FieldArray

Examples

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

In [35]: GF.Random((2,5))
Out[35]: 
GF([[20, 22, 25,  7, 14],
    [20, 29,  2, 24, 17]], 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.FieldMeta.dtypes.

Returns

A Galois field array of a range of field elements.

Return type

galois.FieldArray

Examples

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

In [37]: GF.Range(10,20)
Out[37]: 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.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 [38]: GF = galois.GF(2**3)

In [39]: a = GF.primitive_element

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

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

Returns

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

Return type

galois.FieldArray

Examples

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

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

In [44]: a = GF.Vector(vec); a
Out[44]: GF([50,  5, 61], order=2^6)

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

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

Returns

A Galois field array of zeros.

Return type

galois.FieldArray

Examples

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

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

  • galois.FieldArray – The upper triangular matrix.

Examples

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

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

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

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

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

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

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 [55]: GF = galois.GF(5)

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

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

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

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

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

# P A = L U
In [61]: np.array_equal(P @ A, L @ U)
Out[61]: True
row_reduce(ncols=None)[source]

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

Row reduction operations

  1. Swap the position of any two rows.

  2. Multiply a row by a non-zero scalar.

  3. 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 [62]: GF = galois.GF(31)

In [63]: A = GF.Random((4,4)); A
Out[63]: 
GF([[25, 11, 27, 29],
    [17, 18,  1, 11],
    [26, 13,  0, 22],
    [ 0, 25, 22, 24]], order=31)

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

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

One column is a linear combination of another.

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

In [67]: A = GF.Random((4,4)); A
Out[67]: 
GF([[ 9, 21, 14, 25],
    [ 2, 16, 14,  8],
    [ 0,  5,  6, 20],
    [ 5, 15, 29,  6]], order=31)

In [68]: A[:,2] = A[:,1] * GF(17); A
Out[68]: 
GF([[ 9, 21, 16, 25],
    [ 2, 16, 24,  8],
    [ 0,  5, 23, 20],
    [ 5, 15,  7,  6]], order=31)

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

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

One row is a linear combination of another.

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

In [72]: A = GF.Random((4,4)); A
Out[72]: 
GF([[24, 28, 10, 20],
    [24, 16,  5, 26],
    [14, 19, 21, 11],
    [ 4,  1, 23,  1]], order=31)

In [73]: A[3,:] = A[2,:] * GF(8); A
Out[73]: 
GF([[24, 28, 10, 20],
    [24, 16,  5, 26],
    [14, 19, 21, 11],
    [19, 28, 13, 26]], order=31)

In [74]: A.row_reduce()
Out[74]: 
GF([[ 1,  0,  0, 30],
    [ 0,  1,  0, 14],
    [ 0,  0,  1, 21],
    [ 0,  0,  0,  0]], order=31)

In [75]: np.linalg.matrix_rank(A)
Out[75]: 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.FieldMeta.dtypes.

Returns

A Galois field array of length-\(m\) vectors over \(\mathrm{GF}(p)\).

Return type

galois.FieldArray

Examples

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

In [77]: a = GF.Random(3); a
Out[77]: GF([28, 30, 19], order=2^6)

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

In [79]: GF.Vector(vec)
Out[79]: GF([28, 30, 19], order=2^6)