galois.FieldArray

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

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

Important

galois.FieldArray is an abstract base class for all Galois field array classes and cannot be instantiated directly. Instead, galois.FieldArray subclasses are created using the class factory galois.GF().

This class is included in the API to allow the user to test if an array is a Galois field array subclass.

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

In [2]: issubclass(GF, galois.FieldArray)
Out[2]: True

In [3]: x = GF([1,2,3]); x
Out[3]: GF([1, 2, 3], order=7)

In [4]: isinstance(x, galois.FieldArray)
Out[4]: True

Notes

galois.FieldArray is an abstract base class and cannot be instantiated directly. Instead, the user creates a galois.FieldArray subclass for the field \(\mathrm{GF}(p^m)\) by calling the class factory galois.GF(), e.g. GF = galois.GF(p**m). In this case, GF is a subclass of galois.FieldArray and an instance of galois.FieldClass, a metaclass that defines special methods and attributes related to the Galois field.

galois.FieldArray, and GF, is a subclass of numpy.ndarray and its constructor x = GF(array_like) has the same syntax as numpy.array(). The returned galois.FieldArray instance x is a numpy.ndarray that is acted upon like any other numpy array, except all arithmetic is performed in \(\mathrm{GF}(p^m)\) not in \(\mathbb{Z}\) or \(\mathbb{R}\).

Examples

Construct the Galois field class for \(\mathrm{GF}(2^8)\) using the class factory galois.GF() and then display some relevant properties of the field. See galois.FieldClass for a complete list of Galois field array class methods and attributes.

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

In [6]: GF256
Out[6]: <class 'numpy.ndarray over GF(2^8)'>

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

Depending on the field’s order, only certain numpy dtypes are supported. See galois.FieldClass.dtypes for more details.

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

Galois field arrays can be created from existing numpy arrays.

In [9]: x = np.array([155, 232, 162, 159,  63,  29, 247, 141,  75, 189], dtype=int)

# Explicit Galois field array creation -- a copy is performed
In [10]: GF256(x)
Out[10]: GF([155, 232, 162, 159,  63,  29, 247, 141,  75, 189], order=2^8)

# Or view an existing numpy array as a Galois field array -- no copy is performed
In [11]: x.view(GF256)
Out[11]: GF([155, 232, 162, 159,  63,  29, 247, 141,  75, 189], order=2^8)

Galois field arrays can also be created explicitly by converting an “array-like” object.

# A scalar GF(2^8) element from its integer representation
In [12]: GF256(37)
Out[12]: GF(37, order=2^8)

# A scalar GF(2^8) element from its polynomial representation
In [13]: GF256("x^5 + x^2 + 1")
Out[13]: GF(37, order=2^8)

# A GF(2^8) array from a list of elements in their integer representation
In [14]: GF256([[142, 27], [92, 253]])
Out[14]: 
GF([[142,  27],
    [ 92, 253]], order=2^8)

# A GF(2^8) array from a list of elements in their integer and polynomial representations
In [15]: GF256([[142, "x^5 + x^2 + 1"], [92, 253]])
Out[15]: 
GF([[142,  37],
    [ 92, 253]], order=2^8)

There’s also an alternate constructor Vector() (and accompanying vector() method) to convert an array of coefficients over \(\mathrm{GF}(p)\) with last dimension \(m\) into Galois field elements in \(\mathrm{GF}(p^m)\).

# A scalar GF(2^8) element from its vector representation
In [16]: GF256.Vector([0, 0, 1, 0, 0, 1, 0, 1])
Out[16]: GF(37, order=2^8)

# A GF(2^8) array from a list of elements in their vector representation
In [17]: GF256.Vector([[[1, 0, 0, 0, 1, 1, 1, 0], [0, 0, 0, 1, 1, 0, 1, 1]], [[0, 1, 0, 1, 1, 1, 0, 0], [1, 1, 1, 1, 1, 1, 0, 1]]])
Out[17]: 
GF([[142,  27],
    [ 92, 253]], order=2^8)

Newly-created arrays will use the smallest unsigned dtype, unless otherwise specified.

In [18]: a = GF256([66, 166, 27, 182, 125]); a
Out[18]: GF([ 66, 166,  27, 182, 125], order=2^8)

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

In [20]: b = GF256([66, 166, 27, 182, 125], dtype=np.int64); b
Out[20]: GF([ 66, 166,  27, 182, 125], order=2^8)

In [21]: b.dtype
Out[21]: dtype('int64')

Constructors

__init__(array[, dtype, copy, order, ndmin])	Creates an array over \(\mathrm{GF}(p^m)\).
Elements([dtype])	Creates a 1-D 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, seed, dtype])	Creates a Galois field array with random field elements.
Range(start, stop[, step, dtype])	Creates a 1-D Galois field array with a range of field elements.
Vandermonde(a, m, n[, dtype])	Creates an \(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

additive_order()	Computes the additive order of each element in \(x\).
characteristic_poly()	Computes the characteristic polynomial of a finite field element \(a\) or a square matrix \(\mathbf{A}\).
column_space()	Computes the column space of the matrix \(\mathbf{A}\).
field_norm()	Computes the field norm \(\mathrm{N}_{L / K}(x)\) of the elements of \(x\).
field_trace()	Computes the field trace \(\mathrm{Tr}_{L / K}(x)\) of the elements of \(x\).
is_quadratic_residue()	Determines if the elements of \(x\) are quadratic residues in the Galois field.
left_null_space()	Computes the left null space of the matrix \(\mathbf{A}\).
lu_decompose()	Decomposes the input array into the product of lower and upper triangular matrices.
minimal_poly()	Computes the minimal polynomial of a finite field element \(a\).
multiplicative_order()	Computes the multiplicative order \(\textrm{ord}(x)\) of each element in \(x\).
null_space()	Computes the null space of the matrix \(\mathbf{A}\).
plu_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.
row_space()	Computes the row space of the matrix \(\mathbf{A}\).
vector([dtype])	Converts the Galois field array over \(\mathrm{GF}(p^m)\) to length-\(m\) vectors over the prime subfield \(\mathrm{GF}(p)\).

Special Methods

__add__(other)	Adds two Galois field arrays element-wise.
__divmod__(other)	Divides two Galois field arrays element-wise and returns the quotient and remainder.
__floordiv__(other)	Divides two Galois field arrays element-wise.
__len__()	Return len(self).
__mod__(other)	Divides two Galois field arrays element-wise and returns the remainder.
__mul__(other)	Multiplies two Galois field arrays element-wise.
__pow__(other)	Exponentiates a Galois field array element-wise.
__sub__(other)	Subtracts two Galois field arrays element-wise.
__truediv__(other)	Divides two Galois field arrays element-wise.

classmethod Elements(dtype=None)

Creates a 1-D 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 unsigned dtype for this class, i.e. the first element in galois.FieldClass.dtypes.

Returns

A 1-D Galois field array of all the field’s elements.

Return type

galois.FieldArray

Examples

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

In [2]: GF.Elements()
Out[2]: 
GF([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15],
   order=2^4)

As usual, Galois field elements can be displayed in either the “integer” (default), “polynomial”, or “power” representation. This can be changed by calling galois.FieldClass.display().

# Permanently set the display mode to "poly"
In [3]: GF.display("poly");

In [4]: GF.Elements()
Out[4]: 
GF([0, 1, α, α + 1, α^2, α^2 + 1, α^2 + α, α^2 + α + 1, α^3, α^3 + 1,
    α^3 + α, α^3 + α + 1, α^3 + α^2, α^3 + α^2 + 1, α^3 + α^2 + α,
    α^3 + α^2 + α + 1], order=2^4)

# Temporarily set the display mode to "power"
In [5]: with GF.display("power"):
   ...:     print(GF.Elements())
   ...: 
GF([0, 1, α, α^4, α^2, α^8, α^5, α^10, α^3, α^14, α^9, α^7, α^6, α^13,
    α^11, α^12], order=2^4)

# Reset the display mode to "int"
In [6]: GF.display();

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 unsigned dtype for this class, i.e. the first element in galois.FieldClass.dtypes.

Returns

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

Return type

galois.FieldArray

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 (int, 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-D array. A 2-tuple, e.g. (M,N), represents a 2-D 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 unsigned dtype for this class, i.e. the first element in galois.FieldClass.dtypes.

Returns

A Galois field array of ones.

Return type

galois.FieldArray

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, seed=None, dtype=None)

Creates a Galois field array with random field elements.

Parameters

• shape (int, 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-D array. A 2-tuple, e.g. (M,N), represents a 2-D array with each element indicating the size in each dimension.

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

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

• seed (int, numpy.random.Generator, optional) – Non-negative integer used to initialize the PRNG. The default is None which means that unpredictable entropy will be pulled from the OS to be used as the seed. A numpy.random.Generator can also be passed. If so, it is used directly when dtype != np.object_. Its state is used to seed random.seed(), otherwise.

• dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest unsigned dtype for this class, i.e. the first element in galois.FieldClass.dtypes.

Returns

A Galois field array of random field elements.

Return type

galois.FieldArray

Examples

Generate a random matrix with an unpredictable seed.

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

In [2]: GF.Random((2,5))
Out[2]: 
GF([[13,  6, 12, 19, 25],
    [ 9,  0, 14,  1, 27]], order=31)

Generate a random array with a specified seed. This produces repeatable outputs.

In [3]: GF.Random(10, seed=123456789)
Out[3]: GF([ 7, 29, 20, 27, 18,  5,  2,  0, 24, 24], order=31)

In [4]: GF.Random(10, seed=123456789)
Out[4]: GF([ 7, 29, 20, 27, 18,  5,  2,  0, 24, 24], order=31)

Generate a group of random arrays with one global seed.

In [5]: rng = np.random.default_rng(123456789)

In [6]: GF.Random(10, seed=rng)
Out[6]: GF([ 7, 29, 20, 27, 18,  5,  2,  0, 24, 24], order=31)

In [7]: GF.Random(10, seed=rng)
Out[7]: GF([20, 15,  3, 28, 22,  0,  5, 10,  1,  0], order=31)

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

Creates a 1-D Galois field array with a range of field elements.

Parameters

• start (int) – The starting Galois field value (inclusive) in its integer representation.

• stop (int) – The stopping Galois field value (exclusive) in its integer representation.

• 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 unsigned dtype for this class, i.e. the first element in galois.FieldClass.dtypes.

Returns

A 1-D Galois field array of a range of field elements.

Return type

galois.FieldArray

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 an \(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 unsigned dtype for this class, i.e. the first element in galois.FieldClass.dtypes.

Returns

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

Return type

galois.FieldArray

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

This function is the inverse operation of the vector() method.

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). By convention, the vectors are ordered from highest degree to 0-th degree.

• dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest unsigned dtype for this class, i.e. the first element in galois.FieldClass.dtypes.

Returns

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

Return type

galois.FieldArray

Examples

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

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

In [3]: a = GF.Vector(vec); a
Out[3]: GF([35, 16, 62], order=2^6)

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

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

classmethod Zeros(shape, dtype=None)

Creates a Galois field array with all zeros.

Parameters

• shape (int, 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-D array. A 2-tuple, e.g. (M,N), represents a 2-D 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 unsigned dtype for this class, i.e. the first element in galois.FieldClass.dtypes.

Returns

A Galois field array of zeros.

Return type

galois.FieldArray

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)

__add__(other)

Adds two Galois field arrays element-wise.

Broadcasting rules apply. Both arrays must be over the same Galois field.

Parameters

other (galois.FieldArray) – The other Galois field array.

Returns

The Galois field array self + other.

Return type

galois.FieldArray

Examples

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

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

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

In [4]: a + b
Out[4]: 
GF([[5, 2, 2, 4, 5],
    [1, 5, 2, 6, 1]], order=7)

__divmod__(other)

Divides two Galois field arrays element-wise and returns the quotient and remainder.

Broadcasting rules apply. Both arrays must be over the same Galois field. In Galois fields, true division and floor division are equivalent. In Galois fields, the remainder is always zero.

Parameters

other (galois.FieldArray) – The other Galois field array.

Returns

• galois.FieldArray – The Galois field array self // other.

• galois.FieldArray – The Galois field array self % other.

Examples

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

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

In [3]: b = GF.Random(5, low=1); b
Out[3]: GF([5, 2, 6, 5, 1], order=7)

In [4]: q, r = divmod(a, b)

In [5]: q, r
Out[5]: 
(GF([[3, 6, 5, 3, 2],
     [4, 0, 4, 6, 2]], order=7),
 GF([[0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0]], order=7))

In [6]: b*q + r
Out[6]: 
GF([[1, 5, 2, 1, 2],
    [6, 0, 3, 2, 2]], order=7)

__floordiv__(other)

Divides two Galois field arrays element-wise.

Broadcasting rules apply. Both arrays must be over the same Galois field. In Galois fields, true division and floor division are equivalent.

Parameters

other (galois.FieldArray) – The other Galois field array.

Returns

The Galois field array self // other.

Return type

galois.FieldArray

Examples

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

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

In [3]: b = GF.Random(5, low=1); b
Out[3]: GF([3, 1, 1, 4, 6], order=7)

In [4]: a // b
Out[4]: 
GF([[6, 0, 0, 5, 1],
    [6, 2, 4, 4, 3]], order=7)

__init__(array, dtype=None, copy=True, order='K', ndmin=0)

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

Parameters

• array (int, str, tuple, list, numpy.ndarray, galois.FieldArray) –

  The input array-like object to be converted to a Galois field array. See the examples section for demonstations of array creation using each input type. See see galois.FieldClass.display() and galois.FieldClass.display_mode for a description of the “integer” and “polynomial” representation of Galois field elements.

  • int: A single integer, which is the “integer representation” of a Galois field element, creates a 0-D array.

  • str: A single string, which is the “polynomial representation” of a Galois field element, creates a 0-D array.

  • tuple, list: A list or tuple (or nested lists/tuples) of ints or strings (which can be mix-and-matched) creates an array of

  Galois field elements from their integer or polynomial representations. * numpy.ndarray, galois.FieldArray: An array of ints creates a copy of the array over this specific field.

• dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest unsigned dtype for this class, i.e. the first element in galois.FieldClass.dtypes.

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

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

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

Returns

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

Return type

galois.FieldArray

__mod__(other)

Divides two Galois field arrays element-wise and returns the remainder.

Broadcasting rules apply. Both arrays must be over the same Galois field. In Galois fields, true division and floor division are equivalent. In Galois fields, the remainder is always zero.

Parameters

other (galois.FieldArray) – The other Galois field array.

Returns

The Galois field array self % other.

Return type

galois.FieldArray

Examples

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

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

In [3]: b = GF.Random(5, low=1); b
Out[3]: GF([2, 5, 5, 5, 3], order=7)

In [4]: a % b
Out[4]: 
GF([[0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]], order=7)

__mul__(other)

Multiplies two Galois field arrays element-wise.

Broadcasting rules apply. Both arrays must be over the same Galois field.

Warning

When both multiplicands are galois.FieldArray, that indicates a Galois field multiplication. When one multiplicand is an integer or integer numpy.ndarray, that indicates a scalar multiplication (repeated addition). Galois field multiplication and scalar multiplication are equivalent in prime fields, but not in extension fields.

Parameters

other (numpy.ndarray, galois.FieldArray) – A numpy.ndarray of integers for scalar multiplication or a galois.FieldArray of Galois field elements for finite field multiplication.

Returns

The Galois field array self * other.

Return type

galois.FieldArray

Examples

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

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

In [3]: b = GF.Random(5); b
Out[3]: GF([6, 0, 5, 4, 4], order=7)

In [4]: a * b
Out[4]: 
GF([[2, 0, 5, 6, 0],
    [0, 0, 1, 6, 4]], order=7)

When both multiplicands are Galois field elements, that indicates a Galois field multiplication.

In [5]: GF = galois.GF(2**4, display="poly")

In [6]: a = GF(7); a
Out[6]: GF(α^2 + α + 1, order=2^4)

In [7]: b = GF(2); b
Out[7]: GF(α, order=2^4)

In [8]: a * b
Out[8]: GF(α^3 + α^2 + α, order=2^4)

When one multiplicand is an integer, that indicates a scalar multiplication (repeated addition).

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

In [10]: a + a
Out[10]: GF(0, order=2^4)

__pow__(other)

Exponentiates a Galois field array element-wise.

Broadcasting rules apply. The first array must be a Galois field array and the second must be an integer or integer array.

Parameters

other (int, numpy.ndarray) – The exponent(s) as an integer or integer array.

Returns

The Galois field array self ** other.

Return type

galois.FieldArray

Examples

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

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

In [3]: b = np.random.default_rng().integers(0, 10, 5); b
Out[3]: array([9, 9, 3, 4, 8])

In [4]: a ** b
Out[4]: 
GF([[1, 6, 6, 0, 4],
    [0, 1, 1, 2, 2]], order=7)

__sub__(other)

Subtracts two Galois field arrays element-wise.

Broadcasting rules apply. Both arrays must be over the same Galois field.

Parameters

other (galois.FieldArray) – The other Galois field array.

Returns

The Galois field array self - other.

Return type

galois.FieldArray

Examples

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

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

In [3]: b = GF.Random(5); b
Out[3]: GF([5, 1, 5, 6, 5], order=7)

In [4]: a - b
Out[4]: 
GF([[6, 1, 1, 2, 4],
    [3, 5, 5, 6, 3]], order=7)

__truediv__(other)

Divides two Galois field arrays element-wise.

Broadcasting rules apply. Both arrays must be over the same Galois field. In Galois fields, true division and floor division are equivalent.

Parameters

other (galois.FieldArray) – The other Galois field array.

Returns

The Galois field array self / other.

Return type

galois.FieldArray

Examples

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

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

In [3]: b = GF.Random(5, low=1); b
Out[3]: GF([1, 2, 3, 1, 6], order=7)

In [4]: a / b
Out[4]: 
GF([[5, 2, 4, 5, 6],
    [2, 2, 4, 1, 5]], order=7)

additive_order()

Computes the additive order of each element in \(x\).

Returns

An integer array of the additive order of each element in \(x\). The return value is a single integer if the input array \(x\) is a scalar.

Return type

numpy.integer, numpy.ndarray

Notes

The additive order \(a\) of \(x\) in \(\mathrm{GF}(p^m)\) is the smallest integer \(a\) such that \(x a = 0\). With the exception of \(0\), the additive order of every element is the finite field’s characteristic.

Examples

Below is the additive order of each element of \(\mathrm{GF}(2^4)\).

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

In [2]: x = GF.Elements(); x
Out[2]: 
GF([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15],
   order=2^4)

In [3]: order = x.additive_order(); order
Out[3]: array([1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2])

In [4]: x*order
Out[4]: GF([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], order=2^4)

characteristic_poly()

Computes the characteristic polynomial of a finite field element \(a\) or a square matrix \(\mathbf{A}\).

This function can be invoked on single finite field elements (scalar 0-D arrays) or square \(n \times n\) matrices (2-D arrays).

Returns

For scalar inputs, the degree-\(m\) characteristic polynomial \(p_a(x)\) of \(a\) over \(\mathrm{GF}(p)\). For square \(n \times n\) matrix inputs, the degree-\(n\) characteristic polynomial \(p_A(x)\) of \(\mathbf{A}\) over \(\mathrm{GF}(p^m)\).

Return type

Poly

Notes

An element \(a\) of \(\mathrm{GF}(p^m)\) has characteristic polynomial \(p_a(x)\) over \(\mathrm{GF}(p)\). The characteristic polynomial when evaluated in \(\mathrm{GF}(p^m)\) annihilates \(a\), i.e. \(p_a(a) = 0\). In prime fields \(\mathrm{GF}(p)\), the characteristic polynomial of \(a\) is simply \(p_a(x) = x - a\).

An \(n \times n\) matrix \(\mathbf{A}\) has characteristic polynomial \(p_A(x) = \textrm{det}(x\mathbf{I} - \mathbf{A})\) over \(\mathrm{GF}(p^m)\). The constant coefficient of the characteristic polynomial is \(\textrm{det}(-\mathbf{A})\). The \(x^{n-1}\) coefficient of the characteristic polynomial is \(-\textrm{Tr}(\mathbf{A})\). The characteristic polynomial annihilates \(\mathbf{A}\), i.e. \(p_A(\mathbf{A}) = \mathbf{0}\).

References

• https://en.wikipedia.org/wiki/Characteristic_polynomial

Examples

The characteristic polynomial of the element \(a\).

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

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

In [3]: poly = a.characteristic_poly(); poly
Out[3]: Poly(x^5 + 2x^4 + 2x^3 + x^2 + 2, GF(3))

# The characteristic polynomial annihilates a
In [4]: poly(a, field=GF)
Out[4]: GF(0, order=3^5)

The characteristic polynomial of the square matrix \(\mathbf{A}\).

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

In [6]: A = GF.Random((3,3)); A
Out[6]: 
GF([[112, 189,  73],
    [ 17, 201, 195],
    [235, 148, 118]], order=3^5)

In [7]: poly = A.characteristic_poly(); poly
Out[7]: Poly(x^3 + 175x^2 + 102x + 240, GF(3^5))

# The x^0 coefficient is det(-A)
In [8]: poly.coeffs[-1] == np.linalg.det(-A)
Out[8]: True

# The x^n-1 coefficient is -Tr(A)
In [9]: poly.coeffs[1] == -np.trace(A)
Out[9]: True

# The characteristic polynomial annihilates the matrix A
In [10]: poly(A, elementwise=False)
Out[10]: 
GF([[0, 0, 0],
    [0, 0, 0],
    [0, 0, 0]], order=3^5)

column_space()

Computes the column space of the matrix \(\mathbf{A}\).

Returns

The column space basis matrix. The rows of the basis matrix are the basis vectors that span the column space. The number of rows of the basis matrix is the dimension of the column space.

Return type

galois.FieldArray

Notes

Given an \(m \times n\) matrix \(\mathbf{A}\) over \(\mathrm{GF}(q)\), the column space of \(\mathbf{A}\) is the vector space \(\{\mathbf{x} \in \mathrm{GF}(q)^m\}\) defined by all linear combinations of the columns of \(\mathbf{A}\). The column space has at most dimension \(\textrm{min}(m, n)\).

The column space has properties \(\mathcal{C}(\mathbf{A}) = \mathcal{R}(\mathbf{A}^T)\) and \(\textrm{dim}(\mathcal{C}(\mathbf{A})) + \textrm{dim}(\mathcal{N}(\mathbf{A})) = n\).

Examples

The column_space() method defines basis vectors (its rows) that span the column space of \(\mathbf{A}\). The dimension of the column space and null space sum to \(n\).

In [1]: m, n = 3, 5

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

In [3]: A = GF.Random((m, n)); A
Out[3]: 
GF([[11, 19, 16, 30, 30],
    [19, 26, 22, 16, 24],
    [10, 11, 18, 11,  7]], order=31)

In [4]: C = A.column_space(); C
Out[4]: 
GF([[1, 0, 0],
    [0, 1, 0],
    [0, 0, 1]], order=31)

In [5]: N = A.null_space(); N
Out[5]: 
GF([[ 1,  0, 15, 10, 24],
    [ 0,  1, 21, 10,  4]], order=31)

In [6]: C.shape[0] + N.shape[0] == n
Out[6]: True

field_norm()

Computes the field norm \(\mathrm{N}_{L / K}(x)\) of the elements of \(x\).

Returns

The field norm of \(x\) in the prime subfield \(\mathrm{GF}(p)\).

Return type

galois.FieldArray

Notes

The self array \(x\) is over the extension field \(L = \mathrm{GF}(p^m)\). The field norm of \(x\) is over the subfield \(K = \mathrm{GF}(p)\). In other words, \(\mathrm{N}_{L / K}(x) : L \rightarrow K\).

For finite fields, since \(L\) is a Galois extension of \(K\), the field norm of \(x\) is defined as a product of the Galois conjugates of \(x\).

\[\mathrm{N}_{L / K}(x) = \prod_{i=0}^{m-1} x^{p^i} = x^{(p^m - 1) / (p - 1)}\]

References

• https://en.wikipedia.org/wiki/Field_norm

Examples

The field norm of the elements of \(\mathrm{GF}(3^2)\) is shown below.

In [1]: GF = galois.GF(3**2, display="poly")

In [2]: x = GF.Elements(); x
Out[2]: GF([0, 1, 2, α, α + 1, α + 2, 2α, 2α + 1, 2α + 2], order=3^2)

In [3]: y = x.field_norm(); y
Out[3]: GF([0, 1, 1, 2, 1, 2, 2, 2, 1], order=3)

field_trace()

Computes the field trace \(\mathrm{Tr}_{L / K}(x)\) of the elements of \(x\).

Returns

The field trace of \(x\) in the prime subfield \(\mathrm{GF}(p)\).

Return type

galois.FieldArray

Notes

The self array \(x\) is over the extension field \(L = \mathrm{GF}(p^m)\). The field trace of \(x\) is over the subfield \(K = \mathrm{GF}(p)\). In other words, \(\mathrm{Tr}_{L / K}(x) : L \rightarrow K\).

For finite fields, since \(L\) is a Galois extension of \(K\), the field trace of \(x\) is defined as a sum of the Galois conjugates of \(x\).

\[\mathrm{Tr}_{L / K}(x) = \sum_{i=0}^{m-1} x^{p^i}\]

References

• https://en.wikipedia.org/wiki/Field_trace

Examples

The field trace of the elements of \(\mathrm{GF}(3^2)\) is shown below.

In [1]: GF = galois.GF(3**2, display="poly")

In [2]: x = GF.Elements(); x
Out[2]: GF([0, 1, 2, α, α + 1, α + 2, 2α, 2α + 1, 2α + 2], order=3^2)

In [3]: y = x.field_trace(); y
Out[3]: GF([0, 2, 1, 1, 0, 2, 2, 1, 0], order=3)

is_quadratic_residue()

Determines if the elements of \(x\) are quadratic residues in the Galois field.

Returns

An boolean array indicating if each element in \(x\) is a quadratic residue. The return value is a single boolean if the input array \(x\) is a scalar.

Return type

numpy.bool_, numpy.ndarray

Notes

An element \(x\) in \(\mathrm{GF}(p^m)\) is a quadratic residue if there exists a \(y\) such that \(y^2 = x\) in the field.

In fields with characteristic 2, every element is a quadratic residue. In fields with characteristic greater than 2, exactly half of the nonzero elements are quadratic residues (and they have two unique square roots).

References

• Section 3.5.1 from https://cacr.uwaterloo.ca/hac/about/chap3.pdf.

Examples

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

In [2]: x = GF.Elements(); x
Out[2]: GF([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10], order=11)

In [3]: x.is_quadratic_residue()
Out[3]: 
array([ True,  True, False,  True,  True,  True, False, False, False,
        True, False])

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

In [5]: x = GF.Elements(); x
Out[5]: 
GF([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15],
   order=2^4)

In [6]: x.is_quadratic_residue()
Out[6]: 
array([ True,  True,  True,  True,  True,  True,  True,  True,  True,
        True,  True,  True,  True,  True,  True,  True])

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

In [8]: x = GF.Elements(); x
Out[8]: 
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], order=3^3)

In [9]: x.is_quadratic_residue()
Out[9]: 
array([ True,  True, False, False, False, False,  True,  True,  True,
        True, False,  True,  True,  True, False,  True,  True, False,
       False, False,  True, False,  True, False, False,  True, False])

left_null_space()

Computes the left null space of the matrix \(\mathbf{A}\).

Returns

The left null space basis matrix. The rows of the basis matrix are the basis vectors that span the left null space. The number of rows of the basis matrix is the dimension of the left null space.

Return type

galois.FieldArray

Notes

Given an \(m \times n\) matrix \(\mathbf{A}\) over \(\mathrm{GF}(q)\), the left null space of \(\mathbf{A}\) is the vector space \(\{\mathbf{x} \in \mathrm{GF}(q)^m\}\) that annihilates the rows of \(\mathbf{A}\), i.e. \(\mathbf{x}\mathbf{A} = \mathbf{0}\).

The left null space has properties \(\mathcal{LN}(\mathbf{A}) = \mathcal{N}(\mathbf{A}^T)\) and \(\textrm{dim}(\mathcal{R}(\mathbf{A})) + \textrm{dim}(\mathcal{LN}(\mathbf{A})) = m\).

Examples

The left_null_space() method defines basis vectors (its rows) that span the left null space of \(\mathbf{A}\). The dimension of the row space and left null space sum to \(m\).

In [1]: m, n = 5, 3

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

In [3]: A = GF.Random((m, n)); A
Out[3]: 
GF([[15, 12, 23],
    [11, 26, 17],
    [22,  1,  9],
    [10, 25, 11],
    [19, 20, 20]], order=31)

In [4]: R = A.row_space(); R
Out[4]: 
GF([[1, 0, 0],
    [0, 1, 0],
    [0, 0, 1]], order=31)

In [5]: LN = A.left_null_space(); LN
Out[5]: 
GF([[ 1,  0, 19,  5, 17],
    [ 0,  1, 18,  3,  8]], order=31)

In [6]: R.shape[0] + LN.shape[0] == m
Out[6]: True

The left null space is the set of vectors that sum the rows to 0.

In [7]: LN @ A
Out[7]: 
GF([[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.

Notes

The LU decomposition of \(\mathbf{A}\) is defined as \(\mathbf{A} = \mathbf{L} \mathbf{U}\).

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

minimal_poly()

Computes the minimal polynomial of a finite field element \(a\).

This function can be invoked only on single finite field elements (scalar 0-D arrays).

Returns

For scalar inputs, the minimal polynomial \(p_a(x)\) of \(a\) over \(\mathrm{GF}(p)\).

Return type

Poly

Notes

An element \(a\) of \(\mathrm{GF}(p^m)\) has minimal polynomial \(p_a(x)\) over \(\mathrm{GF}(p)\). The minimal polynomial when evaluated in \(\mathrm{GF}(p^m)\) annihilates \(a\), i.e. \(p_a(a) = 0\). The minimal polynomial always divides the characteristic polynomial. In prime fields \(\mathrm{GF}(p)\), the minimal polynomial of \(a\) is simply \(p_a(x) = x - a\).

References

• https://en.wikipedia.org/wiki/Minimal_polynomial_(field_theory)

• https://en.wikipedia.org/wiki/Minimal_polynomial_(linear_algebra)

Examples

The characteristic polynomial of the element \(a\).

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

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

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

# The minimal polynomial annihilates a
In [4]: poly(a, field=GF)
Out[4]: GF(0, order=3^5)

# The minimal polynomial always divides the characteristic polynomial
In [5]: a.characteristic_poly() / poly
Out[5]: Poly(1, GF(3))

multiplicative_order()

Computes the multiplicative order \(\textrm{ord}(x)\) of each element in \(x\).

Returns

An integer array of the multiplicative order of each element in \(x\). The return value is a single integer if the input array \(x\) is a scalar.

Return type

numpy.integer, numpy.ndarray

Notes

The multiplicative order \(\textrm{ord}(x) = a\) of \(x\) in \(\mathrm{GF}(p^m)\) is the smallest power \(a\) such that \(x^a = 1\). If \(a = p^m - 1\), \(a\) is said to be a generator of the multiplicative group \(\mathrm{GF}(p^m)^\times\).

The multiplicative order of \(0\) is not defined and will raise an ArithmeticError.

FieldArray.multiplicative_order() should not be confused with FieldClass.order. The former is a method on a Galois field array that returns the multiplicative order of elements. The latter is a property of the field, namely the finite field’s order or size.

Examples

Below is the multiplicative order of each non-zero element of \(\mathrm{GF}(2^4)\). The elements with \(\textrm{ord}(x) = 15\) are multiplicative generators of \(\mathrm{GF}(2^4)^\times\)

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

# The multiplicative order of 0 is not defined
In [2]: x = GF.Range(1, GF.order); x
Out[2]: 
GF([ 1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15],
   order=2^4)

In [3]: order = x.multiplicative_order(); order
Out[3]: array([ 1, 15, 15, 15, 15,  3,  3,  5, 15,  5, 15,  5, 15, 15,  5])

# Elements with order of 15 are the primitive elements (generators) of the field
In [4]: GF.primitive_elements
Out[4]: GF([ 2,  3,  4,  5,  9, 11, 13, 14], order=2^4)

In [5]: x**order
Out[5]: GF([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], order=2^4)

null_space()

Computes the null space of the matrix \(\mathbf{A}\).

Returns

The null space basis matrix. The rows of the basis matrix are the basis vectors that span the null space. The number of rows of the basis matrix is the dimension of the null space.

Return type

galois.FieldArray

Notes

Given an \(m \times n\) matrix \(\mathbf{A}\) over \(\mathrm{GF}(q)\), the null space of \(\mathbf{A}\) is the vector space \(\{\mathbf{x} \in \mathrm{GF}(q)^n\}\) that annihilates the columns of \(\mathbf{A}\), i.e. \(\mathbf{A}\mathbf{x} = \mathbf{0}\).

The null space has properties \(\mathcal{N}(\mathbf{A}) = \mathcal{LN}(\mathbf{A}^T)\) and \(\textrm{dim}(\mathcal{C}(\mathbf{A})) + \textrm{dim}(\mathcal{N}(\mathbf{A})) = n\).

Examples

The null_space() method defines basis vectors (its rows) that span the null space of \(\mathbf{A}\). The dimension of the column space and null space sum to \(n\).

In [1]: m, n = 3, 5

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

In [3]: A = GF.Random((m, n)); A
Out[3]: 
GF([[22,  4,  2, 30, 24],
    [13, 22,  9, 14, 13],
    [13, 15, 30, 22,  2]], order=31)

In [4]: C = A.column_space(); C
Out[4]: 
GF([[1, 0, 0],
    [0, 1, 0],
    [0, 0, 1]], order=31)

In [5]: N = A.null_space(); N
Out[5]: 
GF([[ 1,  0, 19, 26, 27],
    [ 0,  1, 29, 19, 15]], order=31)

In [6]: C.shape[0] + N.shape[0] == n
Out[6]: True

The null space is the set of vectors that sum the columns to 0.

In [7]: A @ N.T
Out[7]: 
GF([[0, 0],
    [0, 0],
    [0, 0]], order=31)

plu_decompose()

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

Returns

• galois.FieldArray – The column permutation matrix.

• galois.FieldArray – The lower triangular matrix.

• galois.FieldArray – The upper triangular matrix.

Notes

The PLU decomposition of \(\mathbf{A}\) is defined as \(\mathbf{A} = \mathbf{P} \mathbf{L} \mathbf{U}\). This is equivalent to \(\mathbf{P}^T \mathbf{A} = \mathbf{L} \mathbf{U}\).

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]: P, L, U = A.plu_decompose()

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

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

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

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

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

row_reduce(ncols=None)

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

In [2]: A = GF.Random((4,4)); A
Out[2]: 
GF([[10, 19, 13,  1],
    [ 1, 23,  7, 19],
    [20, 26,  0,  9],
    [ 7, 20, 16,  4]], 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([[21,  0, 20,  9],
    [23, 19, 16,  5],
    [16,  3, 10, 24],
    [ 4, 22, 21, 20]], order=31)

In [7]: A[:,2] = A[:,1] * GF(17); A
Out[7]: 
GF([[21,  0,  0,  9],
    [23, 19, 13,  5],
    [16,  3, 20, 24],
    [ 4, 22,  2, 20]], 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([[15, 29, 16,  4],
    [24, 29,  4, 19],
    [24, 20, 11, 29],
    [17,  1, 13, 22]], order=31)

In [12]: A[3,:] = A[2,:] * GF(8); A
Out[12]: 
GF([[15, 29, 16,  4],
    [24, 29,  4, 19],
    [24, 20, 11, 29],
    [ 6,  5, 26, 15]], order=31)

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

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

row_space()

Computes the row space of the matrix \(\mathbf{A}\).

Returns

The row space basis matrix. The rows of the basis matrix are the basis vectors that span the row space. The number of rows of the basis matrix is the dimension of the row space.

Return type

galois.FieldArray

Notes

Given an \(m \times n\) matrix \(\mathbf{A}\) over \(\mathrm{GF}(q)\), the row space of \(\mathbf{A}\) is the vector space \(\{\mathbf{x} \in \mathrm{GF}(q)^n\}\) defined by all linear combinations of the rows of \(\mathbf{A}\). The row space has at most dimension \(\textrm{min}(m, n)\).

The row space has properties \(\mathcal{R}(\mathbf{A}) = \mathcal{C}(\mathbf{A}^T)\) and \(\textrm{dim}(\mathcal{R}(\mathbf{A})) + \textrm{dim}(\mathcal{LN}(\mathbf{A})) = m\).

Examples

The row_space() method defines basis vectors (its rows) that span the row space of \(\mathbf{A}\). The dimension of the row space and left null space sum to \(m\).

In [1]: m, n = 5, 3

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

In [3]: A = GF.Random((m, n)); A
Out[3]: 
GF([[ 4, 15,  6],
    [ 0, 18,  3],
    [ 2,  3, 14],
    [24,  3,  2],
    [12, 18,  7]], order=31)

In [4]: R = A.row_space(); R
Out[4]: 
GF([[1, 0, 0],
    [0, 1, 0],
    [0, 0, 1]], order=31)

In [5]: LN = A.left_null_space(); LN
Out[5]: 
GF([[ 1,  0, 16, 20, 19],
    [ 0,  1, 11,  9,  6]], order=31)

In [6]: R.shape[0] + LN.shape[0] == m
Out[6]: True

vector(dtype=None)

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

This function is the inverse operation of the Vector() constructor. For an array with shape (n1, n2), the output shape is (n1, n2, m). By convention, the vectors are ordered from highest degree to 0-th degree.

Parameters

dtype (numpy.dtype, optional) – The numpy.dtype of the array elements. The default is None which represents the smallest unsigned dtype for this class, i.e. the first element in galois.FieldClass.dtypes.

Returns

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

Return type

galois.FieldArray

Examples

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

In [2]: a = GF.Random(3); a
Out[2]: GF([62, 49, 15], order=2^6)

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

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

In [5]: GF.Vector(vec)
Out[5]: GF([62, 49, 15], order=2^6)