galois.GFArray¶
-
class
galois.
GFArray
(array, dtype=None, copy=True, order='K', ndmin=0)[source]¶ 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 factorygalois.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 usinggalois.GF
.For example, one can create the \(\mathrm{GF}(7)\) field array class as follows:
In [57]: GF7 = galois.GF(7) In [58]: print(GF7) <class 'numpy.ndarray over GF(7)'>
This subclass can then be used to instantiate arrays over \(\mathrm{GF}(7)\).
In [59]: GF7([3,5,0,2,1]) Out[59]: GF([3, 5, 0, 2, 1], order=7) In [60]: GF7.Random((2,5)) Out[60]: GF([[1, 1, 3, 3, 0], [3, 0, 0, 4, 2]], order=7)
galois.GFArray
is a subclass ofnumpy.ndarray
. Thegalois.GFArray
constructor has the same syntax asnumpy.array
. The returnedgalois.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
ortuple
of ints or strs,int
, orstr
.dtype (numpy.dtype, optional) – The
numpy.dtype
of the array elements. The default isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.copy (bool, optional) – The
copy
keyword argument fromnumpy.array
. The default isTrue
which makes a copy of the input object is it’s an array.order (str, optional) – The
order
keyword argument fromnumpy.array
. Valid values are"K"
(default),"A"
,"C"
, or"F"
.ndmin (int, optional) – The
ndmin
keyword argument fromnumpy.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 [61]: GF256 = galois.GF(2**8); print(GF256) <class 'numpy.ndarray over GF(2^8)'> # Construct a GF(p) class In [62]: GF571 = galois.GF(571); print(GF571) <class 'numpy.ndarray over GF(571)'> # Construct a very large GF(2^m) class In [63]: GF2m = galois.GF(2**100); print(GF2m) <class 'numpy.ndarray over GF(2^100)'> # Construct a very large GF(p) class In [64]: 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 [65]: GF256.dtypes Out[65]: [numpy.uint8, numpy.uint16, numpy.uint32, numpy.int16, numpy.int32, numpy.int64] In [66]: GF571.dtypes Out[66]: [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 asdtype=np.object_
.In [67]: GF2m.dtypes Out[67]: [numpy.object_] In [68]: GFp.dtypes Out[68]: [numpy.object_]
Newly-created arrays will use the smallest, valid dtype.
In [69]: a = GF256.Random(10); a Out[69]: GF([ 72, 235, 117, 55, 255, 239, 39, 163, 180, 33], order=2^8) In [70]: a.dtype Out[70]: dtype('uint8')
This can be explicitly set by specifying the
dtype
keyword argument.In [71]: a = GF256.Random(10, dtype=np.uint32); a Out[71]: GF([243, 27, 175, 87, 102, 193, 54, 159, 67, 51], order=2^8) In [72]: a.dtype Out[72]: dtype('uint32')
Arrays can also be created explicitly by converting an “array-like” object.
# Construct a Galois field array from a list In [73]: l = [142, 27, 92, 253, 103]; l Out[73]: [142, 27, 92, 253, 103] In [74]: GF256(l) Out[74]: GF([142, 27, 92, 253, 103], order=2^8) # Construct a Galois field array from an existing numpy array In [75]: x_np = np.array(l, dtype=np.int64); x_np Out[75]: array([142, 27, 92, 253, 103]) In [76]: GF256(l) Out[76]: 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 [77]: a = x_np.view(GF256); a Out[77]: GF([142, 27, 92, 253, 103], order=2^8) # Changing `x_np` will change `a` In [78]: x_np[0] = 0; x_np Out[78]: array([ 0, 27, 92, 253, 103]) In [79]: a Out[79]: 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\}\).
Eye
(size[, dtype])Creates a 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.
Zeros
(shape[, dtype])Creates a Galois field array with all zeros.
Methods
Decomposes the input array into the product of lower and upper triangular matrices.
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.
-
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 isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.- Returns
A Galois field array of all the field’s elements.
- Return type
Examples
In [80]: GF = galois.GF(31) In [81]: GF.Elements() Out[81]: 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
Eye
(size, dtype=None)[source]¶ Creates a Galois field identity matrix.
- Parameters
size (int) – The size 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 isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
A Galois field identity matrix of shape
(size, size)
.- Return type
Examples
In [82]: GF = galois.GF(31) In [83]: GF.Eye(4) Out[83]: 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, seenumpy.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 isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
A Galois field array of ones.
- Return type
Examples
In [84]: GF = galois.GF(31) In [85]: GF.Ones((2,5)) Out[85]: 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, seenumpy.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 isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
A Galois field array of random field elements.
- Return type
Examples
In [86]: GF = galois.GF(31) In [87]: GF.Random((2,5)) Out[87]: GF([[29, 1, 24, 13, 20], [14, 23, 4, 23, 21]], 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 isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
A Galois field array of a range of field elements.
- Return type
Examples
In [88]: GF = galois.GF(31) In [89]: GF.Range(10,20) Out[89]: GF([10, 11, 12, 13, 14, 15, 16, 17, 18, 19], order=31)
-
classmethod
Zeros
(shape, dtype=None)[source]¶ Creates a Galois field array with all zeros.
- Parameters
shape (tuple) – A numpy-compliant
shape
tuple, seenumpy.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 isNone
which represents the smallest valid dtype for this class, i.e. the first element ingalois.GFMeta.dtypes
.
- Returns
A Galois field array of zeros.
- Return type
Examples
In [90]: GF = galois.GF(31) In [91]: GF.Zeros((2,5)) Out[91]: 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 [92]: GF = galois.GF(5) # Not every square matrix has an LU decomposition In [93]: A = GF([[2, 4, 4, 1], [3, 3, 1, 4], [4, 3, 4, 2], [4, 4, 3, 1]]) In [94]: L, U = A.lu_decompose() In [95]: L Out[95]: GF([[1, 0, 0, 0], [4, 1, 0, 0], [2, 0, 1, 0], [2, 3, 0, 1]], order=5) In [96]: U Out[96]: GF([[2, 4, 4, 1], [0, 2, 0, 0], [0, 0, 1, 0], [0, 0, 0, 4]], order=5) # A = L U In [97]: np.array_equal(A, L @ U) Out[97]: 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 [98]: GF = galois.GF(5) In [99]: A = GF([[1, 3, 2, 0], [3, 4, 2, 3], [0, 2, 1, 4], [4, 3, 3, 1]]) In [100]: L, U, P = A.lup_decompose() In [101]: L Out[101]: GF([[1, 0, 0, 0], [0, 1, 0, 0], [3, 0, 1, 0], [4, 3, 2, 1]], order=5) In [102]: U Out[102]: GF([[1, 3, 2, 0], [0, 2, 1, 4], [0, 0, 1, 3], [0, 0, 0, 3]], order=5) In [103]: P Out[103]: GF([[1, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 1]], order=5) # P A = L U In [104]: np.array_equal(P @ A, L @ U) Out[104]: 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
Examples
In [105]: GF = galois.GF(31) In [106]: A = GF.Random((4,4)); A Out[106]: GF([[22, 7, 26, 20], [14, 6, 27, 0], [ 3, 19, 27, 25], [21, 8, 8, 18]], order=31) In [107]: A.row_reduce() Out[107]: GF([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]], order=31) In [108]: np.linalg.matrix_rank(A) Out[108]: 4
One column is a linear combination of another.
In [109]: GF = galois.GF(31) In [110]: A = GF.Random((4,4)); A Out[110]: GF([[14, 14, 16, 26], [22, 22, 29, 7], [ 6, 0, 7, 20], [19, 5, 21, 11]], order=31) In [111]: A[:,2] = A[:,1] * GF(17); A Out[111]: GF([[14, 14, 21, 26], [22, 22, 2, 7], [ 6, 0, 0, 20], [19, 5, 23, 11]], order=31) In [112]: A.row_reduce() Out[112]: GF([[ 1, 0, 0, 0], [ 0, 1, 17, 0], [ 0, 0, 0, 1], [ 0, 0, 0, 0]], order=31) In [113]: np.linalg.matrix_rank(A) Out[113]: 3
One row is a linear combination of another.
In [114]: GF = galois.GF(31) In [115]: A = GF.Random((4,4)); A Out[115]: GF([[10, 7, 7, 7], [ 6, 9, 5, 1], [19, 28, 3, 9], [16, 6, 8, 27]], order=31) In [116]: A[3,:] = A[2,:] * GF(8); A Out[116]: GF([[10, 7, 7, 7], [ 6, 9, 5, 1], [19, 28, 3, 9], [28, 7, 24, 10]], order=31) In [117]: A.row_reduce() Out[117]: GF([[ 1, 0, 0, 0], [ 0, 1, 0, 30], [ 0, 0, 1, 2], [ 0, 0, 0, 0]], order=31) In [118]: np.linalg.matrix_rank(A) Out[118]: 3