galois.FieldArray¶

class galois.FieldArray(x: ElementLike | ArrayLike, dtype: DTypeLike | None = None, copy: bool = True, order: Literal['K', 'A', 'C', 'F'] = 'K', ndmin: int = 0)¶

A ndarray subclass over \(\mathrm{GF}(p^m)\).

Important

FieldArray is an abstract base class and cannot be instantiated directly. Instead, FieldArray subclasses are created using the class factory GF().

Examples

Create a FieldArray subclass over \(\mathrm{GF}(3^5)\) using the class factory GF().

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

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

In [3]: print(GF.properties)
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

Create a FieldArray instance using GF’s constructor.

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

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

Constructors

`__init__`(x[, dtype, copy, order, ndmin])	Creates an 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 elements.
`Range`(start, stop[, step, dtype])	Creates a 1-D array with a range of elements.
`Vandermonde`(element, rows, cols[, 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\).
`arithmetic_table`(operation[, x, y])	Generates the specified arithmetic table for the finite field.
`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}\).
`compile`(mode)	Recompile the just-in-time compiled ufuncs for a new calculation mode.
`display`([mode])	Sets the display mode for all arrays from this `FieldArray` subclass.
`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.
`primitive_root_of_unity`(n)	Finds a primitive \(n\)-th root of unity in the finite field.
`primitive_roots_of_unity`(n)	Finds all primitive \(n\)-th roots of unity in the finite field.
`repr_table`([element, sort])	Generates a finite field element representation table comparing the power, polynomial, vector, and integer representations.
`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)\).

Attributes

`characteristic`
`default_ufunc_mode`
`degree`
`display_mode`
`dtypes`
`irreducible_poly`
`is_extension_field`
`is_prime_field`
`is_primitive_poly`
`name`
`order`
`ufunc_mode`
`ufunc_modes`

__init__(x: ElementLike | ArrayLike, dtype: DTypeLike | None = None, copy: bool = True, order: Literal['K', 'A', 'C', 'F'] = 'K', ndmin: int = 0)¶

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

Parameters

x: A finite field scalar or array.
dtype: The numpy.dtype of the array elements. The default is None which represents the smallest unsigned data type for this FieldArray subclass (the first element in dtypes).
copy: The copy keyword argument from numpy.array(). The default is True.
order: The order keyword argument from numpy.array(). The default is "K".
ndmin: The ndmin keyword argument from numpy.array(). The default is 0.

classmethod Elements(dtype: DTypeLike | None = None) → FieldArray¶

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

Parameters

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

Returns

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

Examples

Prime field

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)

Extension field

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: int, dtype: DTypeLike | None = None) → FieldArray¶

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

Parameters

size: The size \(n\) along one dimension of the identity matrix.
dtype: The numpy.dtype of the array elements. The default is None which represents the smallest unsigned data type for this FieldArray subclass (the first element in dtypes).

Returns

A 2-D identity matrix with shape (size, size).

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: ShapeLike, dtype: DTypeLike | None = None) → FieldArray¶

Creates an array of all ones.

Parameters

shape: A NumPy-compliant shape tuple.
dtype: The numpy.dtype of the array elements. The default is None which represents the smallest unsigned data type for this FieldArray subclass (the first element in dtypes).

Returns

An array of ones.

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: ShapeLike = (), low: ElementLike = 0, high: ElementLike | None = None, seed: int | Generator | None = None, dtype: DTypeLike | None = None) → FieldArray¶

Creates an array with random elements.

Parameters

shape: A NumPy-compliant shape tuple. The default is () which represents a scalar.
low: The smallest element (inclusive). The default is 0.
high: The largest element (exclusive). The default is None which represents order.
seed: 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: The numpy.dtype of the array elements. The default is None which represents the smallest unsigned data type for this FieldArray subclass (the first element in dtypes).

Returns

An array of random elements.

Examples

Unpredictable seed

Generate a random matrix with an unpredictable seed.

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

In [2]: GF.Random((2, 5))
Out[2]: 
GF([[22, 29, 29, 14,  2],
    [12, 27, 27, 13,  6]], order=31)

Specific seed

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)

Global seed

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: ElementLike, stop: ElementLike, step: int = 1, dtype: DTypeLike | None = None) → FieldArray¶

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

Parameters

start: The starting element (inclusive).
stop: The stopping element (exclusive).
step: The increment between elements. The default is 1.
dtype: The numpy.dtype of the array elements. The default is None which represents the smallest unsigned data type for this FieldArray subclass (the first element in dtypes).

Returns

A 1-D array of a range of elements.

Examples

Prime fields

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)

Extension fields

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(element: ElementLike, rows: int, cols: int, dtype: DTypeLike | None = None) → FieldArray¶

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

Parameters

element: An element \(a\) of \(\mathrm{GF}(q)\).
rows: The number of rows \(m\) in the Vandermonde matrix.
cols: The number of columns \(n\) in the Vandermonde matrix.
dtype: The numpy.dtype of the array elements. The default is None which represents the smallest unsigned data type for this FieldArray subclass (the first element in dtypes).

Returns

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

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: ArrayLike, dtype: DTypeLike | None = None) → FieldArray¶

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: 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 degree \(m-1\) to degree \(0\).
dtype: The numpy.dtype of the array elements. The default is None which represents the smallest unsigned data type for this FieldArray subclass (the first element in dtypes).

Returns

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

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: ShapeLike, dtype: DTypeLike | None = None) → FieldArray¶

Creates an array of all zeros.

Parameters

shape: A NumPy-compliant shape tuple.
dtype: The numpy.dtype of the array elements. The default is None which represents the smallest unsigned data type for this FieldArray subclass (the first element in dtypes).

Returns

An array of zeros.

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__() → str¶

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__() → 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() → integer | ndarray¶

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.

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)

classmethod arithmetic_table(operation: Literal['+', '-', '*', '/'], x: FieldArray | None = None, y: FieldArray | None = None) → str¶

Generates the specified arithmetic table for the finite field.

Parameters

operation: The arithmetic operation.
x: Optionally specify the \(x\) values for the arithmetic table. The default is None which represents \(\{0, \dots, p^m - 1\}\).
y: Optionally specify the \(y\) values for the arithmetic table. The default is None which represents \(\{0, \dots, p^m - 1\}\) for addition, subtraction, and multiplication and \(\{1, \dots, p^m - 1\}\) for division.

Returns

A UTF-8 formatted arithmetic table.

Examples

Arithmetic tables can be displayed using any element representation.

Integer

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

In [2]: print(GF.arithmetic_table("+"))
x + y | 0  1  2  3  4  5  6  7  8 
------|---------------------------
    0 | 0  1  2  3  4  5  6  7  8 
    1 | 1  2  0  4  5  3  7  8  6 
    2 | 2  0  1  5  3  4  8  6  7 
    3 | 3  4  5  6  7  8  0  1  2 
    4 | 4  5  3  7  8  6  1  2  0 
    5 | 5  3  4  8  6  7  2  0  1 
    6 | 6  7  8  0  1  2  3  4  5 
    7 | 7  8  6  1  2  0  4  5  3 
    8 | 8  6  7  2  0  1  5  3  4 

Polynomial

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

In [4]: print(GF.arithmetic_table("+"))
 x + y |      0       1       2       α   α + 1   α + 2      2α  2α + 1  2α + 2 
-------|------------------------------------------------------------------------
     0 |      0       1       2       α   α + 1   α + 2      2α  2α + 1  2α + 2 
     1 |      1       2       0   α + 1   α + 2       α  2α + 1  2α + 2      2α 
     2 |      2       0       1   α + 2       α   α + 1  2α + 2      2α  2α + 1 
     α |      α   α + 1   α + 2      2α  2α + 1  2α + 2       0       1       2 
 α + 1 |  α + 1   α + 2       α  2α + 1  2α + 2      2α       1       2       0 
 α + 2 |  α + 2       α   α + 1  2α + 2      2α  2α + 1       2       0       1 
    2α |     2α  2α + 1  2α + 2       0       1       2       α   α + 1   α + 2 
2α + 1 | 2α + 1  2α + 2      2α       1       2       0   α + 1   α + 2       α 
2α + 2 | 2α + 2      2α  2α + 1       2       0       1   α + 2       α   α + 1 

Power

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

In [6]: print(GF.arithmetic_table("+"))
x + y |   0    1    α  α^2  α^3  α^4  α^5  α^6  α^7 
------|---------------------------------------------
    0 |   0    1    α  α^2  α^3  α^4  α^5  α^6  α^7 
    1 |   1  α^4  α^2  α^7  α^6    0  α^3  α^5    α 
    α |   α  α^2  α^5  α^3    1  α^7    0  α^4  α^6 
  α^2 | α^2  α^7  α^3  α^6  α^4    α    1    0  α^5 
  α^3 | α^3  α^6    1  α^4  α^7  α^5  α^2    α    0 
  α^4 | α^4    0  α^7    α  α^5    1  α^6  α^3  α^2 
  α^5 | α^5  α^3    0    1  α^2  α^6    α  α^7  α^4 
  α^6 | α^6  α^5  α^4    0    α  α^3  α^7  α^2    1 
  α^7 | α^7    α  α^6  α^5    0  α^2  α^4    1  α^3 

An arithmetic table may also be constructed from arbitrary \(x\) and \(y\).

Integer

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

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

In [9]: y = GF([1, 4]); y
Out[9]: GF([1, 4], order=3^2)

In [10]: print(GF.arithmetic_table("+", x=x, y=y))
x + y | 1  4 
------|------
    7 | 8  2 
    2 | 0  3 
    8 | 6  0 

Polynomial

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

In [12]: x = GF([7, 2, 8]); x
Out[12]: GF([2α + 1,      2, 2α + 2], order=3^2)

In [13]: y = GF([1, 4]); y
Out[13]: GF([    1, α + 1], order=3^2)

In [14]: print(GF.arithmetic_table("+", x=x, y=y))
 x + y |      1   α + 1 
-------|----------------
2α + 1 | 2α + 2       2 
     2 |      0       α 
2α + 2 |     2α       0 

Power

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

In [16]: x = GF([7, 2, 8]); x
Out[16]: GF([α^3, α^4, α^6], order=3^2)

In [17]: y = GF([1, 4]); y
Out[17]: GF([  1, α^2], order=3^2)

In [18]: print(GF.arithmetic_table("+", x=x, y=y))
x + y |   1  α^2 
------|----------
  α^3 | α^6  α^4 
  α^4 |   0    α 
  α^6 | α^5    0 

characteristic_poly() → 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)\).

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

Element

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

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

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

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

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

Matrix

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([[149, 181,  24],
    [239, 230, 184],
    [236,  27,  99]], order=3^5)

In [7]: poly = A.characteristic_poly(); poly
Out[7]: Poly(x^3 + 239x^2 + 154x + 185, 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() → FieldArray¶

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.

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([[27, 16,  0, 13,  3],
    [ 1, 20, 17, 19, 27],
    [30, 26, 12, 28, 15]], 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, 11, 20, 18],
    [ 0,  1, 29, 18, 20]], order=31)

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

classmethod compile(mode: Literal['auto', 'jit-lookup', 'jit-calculate', 'python-calculate'])¶

Recompile the just-in-time compiled ufuncs for a new calculation mode.

This function updates ufunc_mode.

Parameters

mode

The ufunc calculation mode.

"auto": Selects "jit-lookup" for fields with order less than \(2^{20}\), "jit-calculate" for larger fields, and "python-calculate" for fields whose elements cannot be represented with numpy.int64.
"jit-lookup": JIT compiles arithmetic ufuncs to use Zech log, log, and anti-log lookup tables for efficient computation. In the few cases where explicit calculation is faster than table lookup, explicit calculation is used.
"jit-calculate": JIT compiles arithmetic ufuncs to use explicit calculation. The "jit-calculate" mode is designed for large fields that cannot or should not store lookup tables in RAM. Generally, the "jit-calculate" mode is slower than "jit-lookup".
"python-calculate": Uses pure-Python ufuncs with explicit calculation. This is reserved for fields whose elements cannot be represented with numpy.int64 and instead use numpy.object_ with Python int (which has arbitrary precision).

classmethod display(mode: Literal['int', 'poly', 'power'] = 'int') → Generator[None, None, None]¶

Sets the display mode for all arrays from this FieldArray subclass.

The display mode can be set to either the integer representation, polynomial representation, or power representation. See Element Representation for a further discussion.

This function updates display_mode.

Warning

For the power representation, numpy.log() is computed on each element. So for large fields without lookup tables, displaying arrays in the power representation may take longer than expected.

Parameters

mode

The field element representation.

"int": Sets the display mode to the integer representation.
"poly": Sets the display mode to the polynomial representation.
"power": Sets the display mode to the power representation.

Returns

A context manager for use in a with statement. If permanently setting the display mode, disregard the return value.

Examples

The default display mode is the integer representation.

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

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

Permanently set the display mode by calling display().

Polynomial

In [3]: GF.display("poly");

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

Power

In [5]: GF.display("power");

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

Temporarily modify the display mode by using display() as a context manager.

Polynomial

In [7]: print(x)
[0, 1, 2, 3, 4, 5, 6, 7, 8]

In [8]: with GF.display("poly"):
   ...:     print(x)
   ...: 
[     0,      1,      2,      α,  α + 1,  α + 2,     2α, 2α + 1, 2α + 2]

# Outside the context manager, the display mode reverts to its previous value
In [9]: print(x)
[0, 1, 2, 3, 4, 5, 6, 7, 8]

Power

In [10]: print(x)
[0, 1, 2, 3, 4, 5, 6, 7, 8]

In [11]: with GF.display("power"):
   ....:     print(x)
   ....: 
[  0,   1, α^4,   α, α^2, α^7, α^5, α^3, α^6]

# Outside the context manager, the display mode reverts to its previous value
In [12]: print(x)
[0, 1, 2, 3, 4, 5, 6, 7, 8]

field_norm() → FieldArray¶

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

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() → FieldArray¶

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

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() → bool_ | ndarray¶

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.

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

Characteristic 2

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

Characteristic > 2

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() → FieldArray¶

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.

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([[ 8, 15,  5],
    [23, 15, 12],
    [21, 11, 18],
    [30, 19, 27],
    [25, 21,  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,  6,  5,  0, 16],
    [ 0,  0,  0,  1,  5]], 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() → Tuple[FieldArray, FieldArray]¶

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

Returns

L – The lower triangular matrix.
U – 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(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() → 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)\).

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

Examples

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

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

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

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

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.
Raises: ArithmeticError – If zero is provided as an input. The multiplicative order of 0 is not defined. There is no power of 0 that ever results in 1.

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

multiplicative_order() should not be confused with order. The former returns the multiplicative order of FieldArray 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() → FieldArray¶

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.

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([[10, 16, 16,  6, 24],
    [10, 30,  1, 14, 23],
    [26, 22, 10, 21,  4]], 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, 22, 15,  7],
    [ 0,  1, 15,  8,  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() → Tuple[FieldArray, FieldArray, FieldArray]¶

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.

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

classmethod primitive_root_of_unity(n: int) → FieldArray¶

Finds a primitive \(n\)-th root of unity in the finite field.

Parameters

n: The root of unity.

Returns

The primitive \(n\)-th root of unity, a 0-D scalar array.

Raises

ValueError – If no primitive \(n\)-th roots of unity exist. This happens when \(n\) is not a divisor of \(p^m - 1\).

Notes

A primitive \(n\)-th root of unity \(\omega_n\) is such that \(\omega_n^n = 1\) and \(\omega_n^k \ne 1\) for all \(1 \le k \lt n\).

In \(\mathrm{GF}(p^m)\), a primitive \(n\)-th root of unity exists when \(n\) divides \(p^m - 1\). Then, the primitive root is \(\omega_n = \alpha^{(p^m - 1)/n}\) where \(\alpha\) is a primitive element of the field.

Examples

In \(\mathrm{GF}(31)\), primitive roots exist for all divisors of \(30\).

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

In [2]: GF.primitive_root_of_unity(2)
Out[2]: GF(30, order=31)

In [3]: GF.primitive_root_of_unity(5)
Out[3]: GF(16, order=31)

In [4]: GF.primitive_root_of_unity(15)
Out[4]: GF(9, order=31)

However, they do not exist for \(n\) that do not divide \(30\).

In [5]: GF.primitive_root_of_unity(7)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Input In [5], in <cell line: 1>()
----> 1 GF.primitive_root_of_unity(7)

File ~/checkouts/readthedocs.org/user_builds/galois/checkouts/v0.0.30/galois/_fields/_array.py:1243, in FieldArray.primitive_root_of_unity(cls, n)
   1241     raise ValueError(f"Argument `n` must be in [1, {cls.order}), not {n}.")
   1242 if not (cls.order - 1) % n == 0:
-> 1243     raise ValueError(f"There are no primitive {n}-th roots of unity in {cls.name}.")
   1245 return cls.primitive_element ** ((cls.order - 1) // n)

ValueError: There are no primitive 7-th roots of unity in GF(31).

For \(\omega_5\), one can see that \(\omega_5^5 = 1\) and \(\omega_5^k \ne 1\) for \(1 \le k \lt 5\).

In [6]: root = GF.primitive_root_of_unity(5); root
Out[6]: GF(16, order=31)

In [7]: np.power.outer(root, np.arange(1, 5 + 1))
Out[7]: GF([16,  8,  4,  2,  1], order=31)

classmethod primitive_roots_of_unity(n: int) → FieldArray¶

Finds all primitive \(n\)-th roots of unity in the finite field.

Parameters

n: The root of unity.

Returns

All primitive \(n\)-th roots of unity, a 1-D array. The roots are sorted in lexicographically-increasing order.

Raises

ValueError – If no primitive \(n\)-th roots of unity exist. This happens when \(n\) is not a divisor of \(p^m - 1\).

Notes

A primitive \(n\)-th root of unity \(\omega_n\) is such that \(\omega_n^n = 1\) and \(\omega_n^k \ne 1\) for all \(1 \le k \lt n\).

In \(\mathrm{GF}(p^m)\), a primitive \(n\)-th root of unity exists when \(n\) divides \(p^m - 1\). Then, the primitive root is \(\omega_n = \alpha^{(p^m - 1)/n}\) where \(\alpha\) is a primitive element of the field.

Examples

In \(\mathrm{GF}(31)\), primitive roots exist for all divisors of \(30\).

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

In [2]: GF.primitive_roots_of_unity(2)
Out[2]: GF([30], order=31)

In [3]: GF.primitive_roots_of_unity(5)
Out[3]: GF([ 2,  4,  8, 16], order=31)

In [4]: GF.primitive_roots_of_unity(15)
Out[4]: GF([ 7,  9, 10, 14, 18, 19, 20, 28], order=31)

However, they do not exist for \(n\) that do not divide \(30\).

In [5]: GF.primitive_roots_of_unity(7)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Input In [5], in <cell line: 1>()
----> 1 GF.primitive_roots_of_unity(7)

File ~/checkouts/readthedocs.org/user_builds/galois/checkouts/v0.0.30/galois/_fields/_array.py:1306, in FieldArray.primitive_roots_of_unity(cls, n)
   1304     raise TypeError(f"Argument `n` must be an int, not {type(n)!r}.")
   1305 if not (cls.order - 1) % n == 0:
-> 1306     raise ValueError(f"There are no primitive {n}-th roots of unity in {cls.name}.")
   1308 roots = np.unique(cls.primitive_elements ** ((cls.order - 1) // n))
   1309 roots = np.sort(roots)

ValueError: There are no primitive 7-th roots of unity in GF(31).

For \(\omega_5\), one can see that \(\omega_5^5 = 1\) and \(\omega_5^k \ne 1\) for \(1 \le k \lt 5\).

In [6]: root = GF.primitive_roots_of_unity(5); root
Out[6]: GF([ 2,  4,  8, 16], order=31)

In [7]: np.power.outer(root, np.arange(1, 5 + 1))
Out[7]: 
GF([[ 2,  4,  8, 16,  1],
    [ 4, 16,  2,  8,  1],
    [ 8,  2, 16,  4,  1],
    [16,  8,  4,  2,  1]], order=31)

classmethod repr_table(element: ElementLike | None = None, sort: Literal['power', 'poly', 'vector', 'int'] = 'power') → str¶

Generates a finite field element representation table comparing the power, polynomial, vector, and integer representations.

Parameters

element: An element to use as the exponent base in the power representation. The default is None which corresponds to primitive_element.
sort: The sorting method for the table. The default is "power". Sorting by "power" will order the rows of the table by ascending powers of element. Sorting by any of the others will order the rows in lexicographically-increasing polynomial/vector order, which is equivalent to ascending order of the integer representation.

Returns

A UTF-8 formatted table comparing the power, polynomial, vector, and integer representations of each field element.

Examples

Create a FieldArray subclass for \(\mathrm{GF}(2^4)\).

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

In [2]: print(GF.properties)
Galois Field:
  name: GF(2^4)
  characteristic: 2
  degree: 4
  order: 16
  irreducible_poly: x^4 + x + 1
  is_primitive_poly: True
  primitive_element: x

Default

Generate a representation table for \(\mathrm{GF}(2^4)\). Since \(x^4 + x + 1\) is a primitive polynomial, \(x\) is a primitive element of the field. Notice, \(\textrm{ord}(x) = 15\).

In [3]: print(GF.repr_table())
 Power       Polynomial         Vector      Integer 
------- ------------------- -------------- ---------
   0             0           [0, 0, 0, 0]      0     
  x^0            1           [0, 0, 0, 1]      1     
  x^1            x           [0, 0, 1, 0]      2     
  x^2           x^2          [0, 1, 0, 0]      4     
  x^3           x^3          [1, 0, 0, 0]      8     
  x^4          x + 1         [0, 0, 1, 1]      3     
  x^5         x^2 + x        [0, 1, 1, 0]      6     
  x^6        x^3 + x^2       [1, 1, 0, 0]      12    
  x^7       x^3 + x + 1      [1, 0, 1, 1]      11    
  x^8         x^2 + 1        [0, 1, 0, 1]      5     
  x^9         x^3 + x        [1, 0, 1, 0]      10    
  x^10      x^2 + x + 1      [0, 1, 1, 1]      7     
  x^11     x^3 + x^2 + x     [1, 1, 1, 0]      14    
  x^12   x^3 + x^2 + x + 1   [1, 1, 1, 1]      15    
  x^13     x^3 + x^2 + 1     [1, 1, 0, 1]      13    
  x^14        x^3 + 1        [1, 0, 0, 1]      9     

Primitive element

Generate a representation table for \(\mathrm{GF}(2^4)\) using a different primitive element \(x^3 + x^2 + x\). Notice, \(\textrm{ord}(x^3 + x^2 + x) = 15\).

In [4]: print(GF.repr_table("x^3 + x^2 + x"))
       Power              Polynomial         Vector      Integer 
-------------------- ------------------- -------------- ---------
         0                    0           [0, 0, 0, 0]      0     
 (x^3 + x^2 + x)^0            1           [0, 0, 0, 1]      1     
 (x^3 + x^2 + x)^1      x^3 + x^2 + x     [1, 1, 1, 0]      14    
 (x^3 + x^2 + x)^2       x^3 + x + 1      [1, 0, 1, 1]      11    
 (x^3 + x^2 + x)^3           x^3          [1, 0, 0, 0]      8     
 (x^3 + x^2 + x)^4         x^3 + 1        [1, 0, 0, 1]      9     
 (x^3 + x^2 + x)^5       x^2 + x + 1      [0, 1, 1, 1]      7     
 (x^3 + x^2 + x)^6        x^3 + x^2       [1, 1, 0, 0]      12    
 (x^3 + x^2 + x)^7           x^2          [0, 1, 0, 0]      4     
 (x^3 + x^2 + x)^8      x^3 + x^2 + 1     [1, 1, 0, 1]      13    
 (x^3 + x^2 + x)^9         x^3 + x        [1, 0, 1, 0]      10    
 (x^3 + x^2 + x)^10        x^2 + x        [0, 1, 1, 0]      6     
 (x^3 + x^2 + x)^11           x           [0, 0, 1, 0]      2     
 (x^3 + x^2 + x)^12   x^3 + x^2 + x + 1   [1, 1, 1, 1]      15    
 (x^3 + x^2 + x)^13        x^2 + 1        [0, 1, 0, 1]      5     
 (x^3 + x^2 + x)^14         x + 1         [0, 0, 1, 1]      3     

Non-primitive element

Generate a representation table for \(\mathrm{GF}(2^4)\) using a non-primitive element \(x^3 + x^2\). Notice, \(\textrm{ord}(x^3 + x^2) = 5 \ne 15\).

In [5]: print(GF.repr_table("x^3 + x^2"))
     Power            Polynomial         Vector      Integer 
---------------- ------------------- -------------- ---------
       0                  0           [0, 0, 0, 0]      0     
 (x^3 + x^2)^0            1           [0, 0, 0, 1]      1     
 (x^3 + x^2)^1        x^3 + x^2       [1, 1, 0, 0]      12    
 (x^3 + x^2)^2    x^3 + x^2 + x + 1   [1, 1, 1, 1]      15    
 (x^3 + x^2)^3           x^3          [1, 0, 0, 0]      8     
 (x^3 + x^2)^4         x^3 + x        [1, 0, 1, 0]      10    
 (x^3 + x^2)^5            1           [0, 0, 0, 1]      1     
 (x^3 + x^2)^6        x^3 + x^2       [1, 1, 0, 0]      12    
 (x^3 + x^2)^7    x^3 + x^2 + x + 1   [1, 1, 1, 1]      15    
 (x^3 + x^2)^8           x^3          [1, 0, 0, 0]      8     
 (x^3 + x^2)^9         x^3 + x        [1, 0, 1, 0]      10    
 (x^3 + x^2)^10           1           [0, 0, 0, 1]      1     
 (x^3 + x^2)^11       x^3 + x^2       [1, 1, 0, 0]      12    
 (x^3 + x^2)^12   x^3 + x^2 + x + 1   [1, 1, 1, 1]      15    
 (x^3 + x^2)^13          x^3          [1, 0, 0, 0]      8     
 (x^3 + x^2)^14        x^3 + x        [1, 0, 1, 0]      10    

row_reduce(ncols: int | None = None) → FieldArray¶

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

Parameters

ncols: 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.

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() → FieldArray¶

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.

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([[16, 26, 30],
    [23, 21,  0],
    [15,  1, 22],
    [16,  4, 30],
    [11,  4, 27]], 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,  4, 23, 16],
    [ 0,  1,  0, 24, 25]], order=31)

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

vector(dtype: DTypeLike | None = None) → FieldArray¶

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 degree \(m-1\) to degree \(0\).

Parameters

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

Returns

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

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)

class property characteristic : int¶

The prime characteristic \(p\) of the Galois field \(\mathrm{GF}(p^m)\). Adding \(p\) copies of any element will always result in \(0\).

Examples

In [1]: galois.GF(2).characteristic
Out[1]: 2

In [2]: galois.GF(2**8).characteristic
Out[2]: 2

In [3]: galois.GF(31).characteristic
Out[3]: 31

In [4]: galois.GF(7**5).characteristic
Out[4]: 7

class property default_ufunc_mode : Literal['jit-lookup', 'jit-calculate', 'python-calculate']¶

The default ufunc compilation mode for this FieldArray subclass. The ufuncs may be recompiled with compile().

Examples

Small fields

Fields with order less than \(2^{20}\) are compiled, by default, using lookup tables for speed.

In [1]: galois.GF(65537).default_ufunc_mode
Out[1]: 'jit-lookup'

In [2]: galois.GF(2**16).default_ufunc_mode
Out[2]: 'jit-lookup'

Medium fields

Fields with order greater than \(2^{20}\) are compiled, by default, using explicit calculation for memory savings. The field elements and arithmetic must still fit within numpy.int64.

In [3]: galois.GF(2147483647).default_ufunc_mode
Out[3]: 'jit-calculate'

In [4]: galois.GF(2**32).default_ufunc_mode
Out[4]: 'jit-calculate'

Large fields

Fields whose elements and arithmetic cannot fit within numpy.int64 use pure-Python explicit calculation.

In [5]: galois.GF(36893488147419103183).default_ufunc_mode
Out[5]: 'python-calculate'

In [6]: galois.GF(2**100).default_ufunc_mode
Out[6]: 'python-calculate'

class property degree : int¶

The extension degree \(m\) of the Galois field \(\mathrm{GF}(p^m)\). The degree is a positive integer.

Examples

In [1]: galois.GF(2).degree
Out[1]: 1

In [2]: galois.GF(2**8).degree
Out[2]: 8

In [3]: galois.GF(31).degree
Out[3]: 1

In [4]: galois.GF(7**5).degree
Out[4]: 5

class property display_mode : Literal['int', 'poly', 'power']¶

The current finite field element representation. This can be changed with display().

See Element Representation for a further discussion.

Examples

The default display mode is the integer representation.

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

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

In [3]: GF.display_mode
Out[3]: 'int'

Permanently modify the display mode by calling display().

In [4]: GF.display("poly");

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

In [6]: GF.display_mode
Out[6]: 'poly'

class property dtypes : List[numpy.dtype]¶

List of valid integer numpy.dtype values that are compatible with this finite field. Creating an array with an unsupported dtype will raise a TypeError exception.

For finite fields whose elements cannot be represented with numpy.int64, the only valid data type is numpy.object_.

Examples

Some data types are too small for certain finite fields, such as numpy.int16 for \(\mathrm{GF}(7^5)\).

In [1]: GF = galois.GF(31); GF.dtypes
Out[1]: 
[numpy.uint8,
 numpy.uint16,
 numpy.uint32,
 numpy.int8,
 numpy.int16,
 numpy.int32,
 numpy.int64]

In [2]: GF = galois.GF(7**5); GF.dtypes
Out[2]: [numpy.uint16, numpy.uint32, numpy.int16, numpy.int32, numpy.int64]

Large fields must use numpy.object_ which uses Python int for its unlimited size.

In [3]: GF = galois.GF(2**100); GF.dtypes
Out[3]: [numpy.object_]

In [4]: GF = galois.GF(36893488147419103183); GF.dtypes
Out[4]: [numpy.object_]

class property irreducible_poly : Poly¶

The irreducible polynomial \(f(x)\) of the Galois field \(\mathrm{GF}(p^m)\). The irreducible polynomial is of degree \(m\) over \(\mathrm{GF}(p)\).

Examples

In [1]: galois.GF(2).irreducible_poly
Out[1]: Poly(x + 1, GF(2))

In [2]: galois.GF(2**8).irreducible_poly
Out[2]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))

In [3]: galois.GF(31).irreducible_poly
Out[3]: Poly(x + 28, GF(31))

In [4]: galois.GF(7**5).irreducible_poly
Out[4]: Poly(x^5 + x + 4, GF(7))

class property is_extension_field : bool¶

Indicates if the finite field is an extension field. This is true when the field’s order is a prime power.

Examples

In [1]: galois.GF(2).is_extension_field
Out[1]: False

In [2]: galois.GF(2**8).is_extension_field
Out[2]: True

In [3]: galois.GF(31).is_extension_field
Out[3]: False

In [4]: galois.GF(7**5).is_extension_field
Out[4]: True

class property is_prime_field : bool¶

Indicates if the finite field is a prime field, not an extension field. This is true when the field’s order is prime.

Examples

In [1]: galois.GF(2).is_prime_field
Out[1]: True

In [2]: galois.GF(2**8).is_prime_field
Out[2]: False

In [3]: galois.GF(31).is_prime_field
Out[3]: True

In [4]: galois.GF(7**5).is_prime_field
Out[4]: False

class property is_primitive_poly : bool¶

Indicates whether the irreducible_poly is a primitive polynomial. If so, \(x\) is a primitive element of the finite field.

Examples

The default \(\mathrm{GF}(2^8)\) field uses a primitive polynomial.

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

In [2]: GF.is_primitive_poly
Out[2]: True

The \(\mathrm{GF}(2^8)\) field from AES uses a non-primitive polynomial.

In [3]: GF = galois.GF(2**8, irreducible_poly="x^8 + x^4 + x^3 + x + 1")

In [4]: GF.is_primitive_poly
Out[4]: False

class property name : str¶

The finite field’s name as a string GF(p) or GF(p^m).

Examples

In [1]: galois.GF(2).name
Out[1]: 'GF(2)'

In [2]: galois.GF(2**8).name
Out[2]: 'GF(2^8)'

In [3]: galois.GF(31).name
Out[3]: 'GF(31)'

In [4]: galois.GF(7**5).name
Out[4]: 'GF(7^5)'

class property order : int¶

The order \(p^m\) of the Galois field \(\mathrm{GF}(p^m)\). The order of the field is equal to the field’s size.

Examples

In [1]: galois.GF(2).order
Out[1]: 2

In [2]: galois.GF(2**8).order
Out[2]: 256

In [3]: galois.GF(31).order
Out[3]: 31

In [4]: galois.GF(7**5).order
Out[4]: 16807

class property prime_subfield : Type[FieldArray]¶

The prime subfield \(\mathrm{GF}(p)\) of the extension field \(\mathrm{GF}(p^m)\).

Examples

In [1]: galois.GF(2).prime_subfield
Out[1]: galois.GF2

In [2]: galois.GF(2**8).prime_subfield
Out[2]: galois.GF2

In [3]: galois.GF(31).prime_subfield
Out[3]: galois.GF(31)

In [4]: galois.GF(7**5).prime_subfield
Out[4]: galois.GF(7)

class property primitive_element : FieldArray¶

A primitive element \(\alpha\) of the Galois field \(\mathrm{GF}(p^m)\). A primitive element is a multiplicative generator of the field, such that \(\mathrm{GF}(p^m) = \{0, 1, \alpha, \alpha^2, \dots, \alpha^{p^m - 2}\}\).

A primitive element is a root of the primitive polynomial \(f(x)\), such that \(f(\alpha) = 0\) over \(\mathrm{GF}(p^m)\).

Examples

In [1]: galois.GF(2).primitive_element
Out[1]: GF(1, order=2)

In [2]: galois.GF(2**8).primitive_element
Out[2]: GF(2, order=2^8)

In [3]: galois.GF(31).primitive_element
Out[3]: GF(3, order=31)

In [4]: galois.GF(7**5).primitive_element
Out[4]: GF(7, order=7^5)

class property primitive_elements : FieldArray¶

All primitive elements \(\alpha\) of the Galois field \(\mathrm{GF}(p^m)\). A primitive element is a multiplicative generator of the field, such that \(\mathrm{GF}(p^m) = \{0, 1, \alpha, \alpha^2, \dots, \alpha^{p^m - 2}\}\).

Examples

In [1]: galois.GF(2).primitive_elements
Out[1]: GF([1], order=2)

In [2]: galois.GF(2**8).primitive_elements
Out[2]: 
GF([  2,   4,   6,   9,  13,  14,  16,  18,  19,  20,  22,  24,  25,  27,
     29,  30,  31,  34,  35,  40,  42,  43,  48,  49,  50,  52,  57,  60,
     63,  65,  66,  67,  71,  72,  73,  74,  75,  76,  81,  82,  83,  84,
     88,  90,  91,  92,  93,  95,  98,  99, 104, 105, 109, 111, 112, 113,
    118, 119, 121, 122, 123, 126, 128, 129, 131, 133, 135, 136, 137, 140,
    141, 142, 144, 148, 149, 151, 154, 155, 157, 158, 159, 162, 163, 164,
    165, 170, 171, 175, 176, 177, 178, 183, 187, 188, 189, 192, 194, 198,
    199, 200, 201, 202, 203, 204, 209, 210, 211, 212, 213, 216, 218, 222,
    224, 225, 227, 229, 232, 234, 236, 238, 240, 243, 246, 247, 248, 249,
    250, 254], order=2^8)

In [3]: galois.GF(31).primitive_elements
Out[3]: GF([ 3, 11, 12, 13, 17, 21, 22, 24], order=31)

In [4]: galois.GF(7**5).primitive_elements
Out[4]: GF([    7,     8,    14, ..., 16797, 16798, 16803], order=7^5)

class property properties : str¶

A formatted string of relevant properties of the Galois field.

Examples

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

In [2]: print(GF.properties)
Galois Field:
  name: GF(7^5)
  characteristic: 7
  degree: 5
  order: 16807
  irreducible_poly: x^5 + x + 4
  is_primitive_poly: True
  primitive_element: x

class property quadratic_non_residues : FieldArray¶

All quadratic non-residues in the Galois field.

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

In fields with characteristic 2, no elements are quadratic non-residues. In fields with characteristic greater than 2, exactly half of the nonzero elements are quadratic non-residues.