galois.FieldArray¶

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

A Galois field 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

See Galois Field Classes for a detailed discussion of the relationship between galois.FieldClass and galois.FieldArray.

See Array Creation for a detailed discussion on creating arrays (with and without copying) from array-like objects, valid NumPy data types, and other galois.FieldArray classmethods.

Examples

Create a Galois field array class using the class factory galois.GF().

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

In [6]: print(GF)
Galois Field:
  name: GF(3^5)
  characteristic: 3
  degree: 5
  order: 243
  irreducible_poly: x^5 + 2x + 1
  is_primitive_poly: True
  primitive_element: x

The Galois field array class GF is a subclass of galois.FieldArray, with galois.FieldClass as its metaclass.

In [7]: isinstance(GF, galois.FieldClass)
Out[7]: True

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

Create a Galois field array using GF’s constructor.

In [9]: x = GF([44, 236, 206, 138]); x
Out[9]: GF([ 44, 236, 206, 138], order=3^5)

The Galois field array x is an instance of the Galois field array class GF.

In [10]: isinstance(x, GF)
Out[10]: True

Constructors

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

Special Methods

__repr__()	Displays the array specifying the class and finite field order.
__str__()	Displays the array without specifying the class or finite field order.

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 finite 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 an array over \(\mathrm{GF}(p^m)\) to length-\(m\) vectors over the prime subfield \(\mathrm{GF}(p)\).

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

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

Parameters

array : Union[int, str, Iterable, numpy.ndarray, galois.FieldArray]

The input array-like object to be converted to a Galois field array. See Array Creation for a detailed discussion about creating new arrays and array-like objects.

• int: A single integer, which is the integer representation of a finite field element, creates a 0-D array (scalar).

• str: A single string, which is the polynomial representation of a finite field element, creates a 0-D array (scalar).

• tuple, list: A list or tuple (or nested lists/tuples) of integers or strings (which can be mixed and matched) creates an array of finite field elements from their integer or polynomial representations.

• numpy.ndarray, galois.FieldArray: A NumPy array of integers creates a copy of the array over this specific field.

dtype : Optional[Union[numpy.dtype, int, object]]

The numpy.dtype of the array elements. The default is None which represents the smallest unsigned data type for this class (the first element in galois.FieldClass.dtypes).

copy : bool

The copy keyword argument from numpy.array(). The default is True which makes a copy of the input array.

order : Literal['K', 'A', 'C', 'F']

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

ndmin : int

The ndmin keyword argument from numpy.array(). The minimum number of dimensions of the output. The default is 0.

classmethod Elements(dtype=None)¶

Creates a 1-D array of the finite field’s elements \(\{0, \dots, p^m-1\}\).

Parameters

dtype : Optional[Union[numpy.dtype, int, object]]

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

Returns

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

Return type

galois.FieldArray

Examples

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

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

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

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

classmethod Identity(size, dtype=None)¶

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

Parameters

size : int

The size \(n\) along one axis of the matrix. The resulting array has shape (size, size).

dtype : Optional[Union[numpy.dtype, int, object]]

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

Returns

A 2-D identity matrix with 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 an array of all ones.

Parameters

shape : Union[int, Sequence[int]]

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 : Optional[Union[numpy.dtype, int, object]]

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

Returns

An 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 an array with random field elements.

Parameters

shape : Union[int, Sequence[int]]

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 : Optional[int]

The smallest finite field element (inclusive) in its integer representation. The default is 0.

high : Optional[int]

The largest finite field element (exclusive) in its integer representation. The default is None which represents the field’s order \(p^m\).

seed : Optional[Union[int, numpy.random._generator.Generator]]

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.

dtype : Optional[Union[numpy.dtype, int, object]]

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

Returns

An array of random finite 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([[25, 25, 19,  4, 25],
    [ 3, 26, 13, 28, 11]], 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 using a single 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 array with a range of field elements.

Parameters

start : int

The starting finite field element (inclusive) in its integer representation.

stop : int

The stopping finite field element (exclusive) in its integer representation.

step : Optional[int]

The increment between finite field element. The default is 1.

dtype : Optional[Union[numpy.dtype, int, object]]

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

Returns

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

Return type

galois.FieldArray

Examples

For prime fields, the increment is simply a finite field element, since all elements are integers.

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)

In [3]: GF.Range(10, 20, 2)
Out[3]: GF([10, 12, 14, 16, 18], order=31)

For extension fields, the increment is the integer increment between finite field elements in their integer representation.

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

In [5]: GF.Range(10, 20)
Out[5]: 
GF([     α^2 + 1,      α^2 + 2,      α^2 + α,  α^2 + α + 1,  α^2 + α + 2,
        α^2 + 2α, α^2 + 2α + 1, α^2 + 2α + 2,         2α^2,     2α^2 + 1],
   order=3^3)

In [6]: GF.Range(10, 20, 2)
Out[6]: 
GF([     α^2 + 1,      α^2 + α,  α^2 + α + 2, α^2 + 2α + 1,         2α^2],
   order=3^3)

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

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

Parameters

a : Union[int, galois.FieldArray]

An element of \(\mathrm{GF}(q)\).

m : int

The number of rows in the Vandermonde matrix.

n : int

The number of columns in the Vandermonde matrix.

dtype : Optional[Union[numpy.dtype, int, object]]

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

Returns

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

Return type

galois.FieldArray

Examples

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

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

In [3]: V = GF.Vandermonde(a, 7, 7); V
Out[3]: 
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 an 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 : Union[Iterable, numpy.ndarray, galois.FieldArray]

An array over \(\mathrm{GF}(p)\) with last dimension \(m\). An 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 : Optional[Union[numpy.dtype, int, object]]

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

Returns

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

Return type

galois.FieldArray

Examples

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

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

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

classmethod Zeros(shape, dtype=None)¶

Creates an array of all zeros.

Parameters

shape : Union[int, Sequence[int]]

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 : Optional[Union[numpy.dtype, int, object]]

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

Returns

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

__repr__()¶

Displays the array specifying the class and finite field order.

This function prepends GF( and appends , order=p^m).

Examples

Integer

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

In [2]: x = GF([4, 2, 7, 5])

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

Polynomial

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

In [5]: x = GF([4, 2, 7, 5])

In [6]: x
Out[6]: GF([ α + 1,      2, 2α + 1,  α + 2], order=3^2)

Power

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

In [8]: x = GF([4, 2, 7, 5])

In [9]: x
Out[9]: GF([α^2, α^4, α^3, α^7], order=3^2)

__str__()¶

Displays the array without specifying the class or finite field order.

This function does not prepend GF( and or append , order=p^m).

Examples

Integer

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

In [2]: x = GF([4, 2, 7, 5])

In [3]: print(x)
[4, 2, 7, 5]

Polynomial

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

In [5]: x = GF([4, 2, 7, 5])

In [6]: print(x)
[ α + 1,      2, 2α + 1,  α + 2]

Power

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

In [8]: x = GF([4, 2, 7, 5])

In [9]: print(x)
[α^2, α^4, α^3, α^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

Union[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}(3^2)\).

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]: order = x.additive_order(); order
Out[3]: array([1, 3, 3, 3, 3, 3, 3, 3, 3])

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

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

galois.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(1, order=3^5)

In [3]: poly = a.characteristic_poly(); poly
Out[3]: Poly(x^5 + x^4 + x^3 + 2x^2 + 2x + 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([[ 68, 154,  14],
    [ 25, 163, 168],
    [160, 130, 200]], order=3^5)

In [7]: poly = A.characteristic_poly(); poly
Out[7]: Poly(x^3 + 178x^2 + 206x + 84, 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([[ 2, 28, 11, 21, 30],
    [10, 23,  6,  0, 25],
    [13,  8,  8,  3, 17]], 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, 30, 29, 11],
    [ 0,  1,  7, 12, 16]], 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 finite field.

Returns

A 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

Union[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

Since \(\mathrm{GF}(2^3)\) has characteristic \(2\), every element has a square root.

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

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

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

In \(\mathrm{GF}(11)\), the characteristic is greater than \(2\) so only half of the elements have square roots.

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

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

In [6]: x.is_quadratic_residue()
Out[6]: 
array([ True,  True, False,  True,  True,  True, False, 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([[ 9, 29,  4],
    [ 3,  5, 17],
    [ 0, 26,  3],
    [23, 29, 18],
    [18, 30, 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, 10,  5,  0],
    [ 0,  1, 10, 19, 10]], 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

• L – The lower triangular matrix.

• U – The upper triangular matrix.

Return type

Tuple[galois.FieldArray, galois.FieldArray]

Notes

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

Examples

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

# Not every square matrix has an LU decomposition
In [2]: A = GF([[22, 11, 25, 11], [30, 27, 10, 3], [21, 16, 29, 7]]); A
Out[2]: 
GF([[22, 11, 25, 11],
    [30, 27, 10,  3],
    [21, 16, 29,  7]], order=31)

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

In [4]: L
Out[4]: 
GF([[ 1,  0,  0],
    [ 7,  1,  0],
    [ 8, 25,  1]], order=31)

In [5]: U
Out[5]: 
GF([[22, 11, 25, 11],
    [ 0, 12, 21, 19],
    [ 0,  0, 17,  2]], order=31)

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

galois.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(15, order=3^5)

In [3]: poly = a.minimal_poly(); poly
Out[3]: Poly(x^5 + x^3 + x + 2, 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

Union[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}(3^2)\).

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

# The multiplicative order of 0 is not defined
In [2]: x = GF.Range(1, GF.order); x
Out[2]: 
GF([     1,      2,      α,  α + 1,  α + 2,     2α, 2α + 1, 2α + 2],
   order=3^2)

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

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

The elements with \(\textrm{ord}(x) = 8\) are multiplicative generators of \(\mathrm{GF}(3^2)^\times\).

In [5]: GF.primitive_elements
Out[5]: GF([     α,  α + 2,     2α, 2α + 1], order=3^2)

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([[28,  6,  7, 25, 27],
    [29,  8,  1, 22, 16],
    [29, 20,  1, 18, 19]], 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,  9, 12],
    [ 0,  1,  7,  9,  8]], 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

• P – The column permutation matrix.

• L – The lower triangular matrix.

• U – The upper triangular matrix.

Return type

Tuple[galois.FieldArray, galois.FieldArray, galois.FieldArray]

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(31)

In [2]: A = GF([[0, 29, 2, 9], [20, 24, 5, 1], [2, 24, 1, 7]]); A
Out[2]: 
GF([[ 0, 29,  2,  9],
    [20, 24,  5,  1],
    [ 2, 24,  1,  7]], order=31)

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

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

In [5]: L
Out[5]: 
GF([[ 1,  0,  0],
    [ 0,  1,  0],
    [28, 14,  1]], order=31)

In [6]: U
Out[6]: 
GF([[20, 24,  5,  1],
    [ 0, 29,  2,  9],
    [ 0,  0, 19,  8]], order=31)

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

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.

Parameters

ncols : Optional[int]

The number of columns to perform Gaussian elimination over. The default is None which represents the number of columns of the matrix.

Returns

The reduced row echelon form of the input matrix.

Return type

galois.FieldArray

Notes

The elementary row operations in Gaussian elimination are: swap the position of any two rows, multiply any row by a non-zero scalar, and add any row to a scalar multiple of another row.

Examples

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

In [2]: A = GF([[16, 12, 1, 25], [1, 10, 27, 29], [1, 0, 3, 19]]); A
Out[2]: 
GF([[16, 12,  1, 25],
    [ 1, 10, 27, 29],
    [ 1,  0,  3, 19]], order=31)

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

In [4]: np.linalg.matrix_rank(A)
Out[4]: 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([[23,  6,  9],
    [10, 25,  4],
    [16,  2, 11],
    [ 7, 28, 11],
    [12, 30, 21]], 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, 27, 17,  9],
    [ 0,  1, 23,  5, 25]], order=31)

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

vector(dtype=None)¶

Converts an 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 : Optional[Union[numpy.dtype, int, object]]

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

Returns

An array over \(\mathrm{GF}(p)\) with last dimension \(m\).

Return type

galois.FieldArray

Examples

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

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

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

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