FiniteField

FiniteField[p,d]

gives a finite field with elements.

FiniteField[p,f]

gives the finite field , where is an irreducible polynomial in .

FiniteField[p,…,rep]

uses field element representation rep, either "Polynomial" or "Exponential".

Details

Finite fields are also known as Galois fields.
Finite fields are used in algebraic computation, error-correcting codes, cryptography, combinatorics, algebraic geometry, number theory and finite geometry.
A field is an algebraic system with all four arithmetic operations +, -, * and ÷. A finite field can have elements for some prime and positive integer .
The element is the additive identity where for all and the element gives the multiplicative identity where for all .

FiniteFieldElement[,k] or [k] can be used to get the element and is formatted as .
FiniteFieldElement objects in the same field are automatically combined by arithmetic operations.
Polynomial operations such as PolynomialGCD, Factor, Expand, PolynomialQuotientRemainder and Resultant can be used for polynomials with coefficients from a finite field. Together and Cancel can be used for rational functions with coefficients from a finite field.
Linear algebra operations such as Det, Inverse, RowReduce, NullSpace, MatrixRank and LinearSolve can be used for matrices with entries from a finite field.
Solve and Reduce can be used to solve systems of equations over finite fields.
There are two different representations rep supported for FiniteField: "Polynomial" and "Exponential".
The "Polynomial" representation is the analog of a Cartesian representation of complex numbers , easy to add and subtract but slightly harder to multiply and divide.
Representation: It uses an irreducible polynomial of degree d to identify the field with the quotient:
.
Each element is represented as a polynomial . Or you can think of it as a vector in the basis .
Enumeration: The elements are enumerated in reverse lexicographic order:
,,…,,…,
Operations: Let and ; then you have:
and
and is reduced modulo (PolynomialRemainder) to degree . with . , and the multiplicative inverse is computed using the extended polynomial GCD. Since is irreducible, you have and hence from the extended polynomial GCD, you have for some polynomials and . By reducing modulo , you get and hence you have .
The "Exponential" representation is the analog of a polar representation of complex number , easy to multiply and divide but slightly harder to add and subtract.
Representation: As in the "Polynomial" representation, it uses an irreducible polynomial of degree d, but in this case also needs to be primitive. Since is primitive, the powers of represent every element in except :
This representation is also known as the cyclic group representation, since is a cyclic group under multiplication.
Enumeration: The elements are enumerated using the power order:
, , , …, , …,
Operations: Let and , then you have:
$u *v=alpha^(TemplateBox[{{(, {i, +, j}, )}, {(, {q, -, 1}, )}}, Mod])$ and
with the inversion . For addition and subtraction, there is no simple rule that gives such that , and so that is stored in a lookup table that is linear in the field size . This makes the operation fast at the cost of storing data. It also means that the "Exponential" representation is not suitable for large fields.
The practical difference between representations is:
"Polynomial" takes no time to create, uses no extra memory, works for large fields but has slightly slower operations.
"Exponential" takes some time to create, uses extra memory proportional to the size of the field, works for small fields but has slightly faster operations.
Information[FiniteField[…], prop] gives the property prop of the finite field. The following properties can be specified:

	"Characteristic"	the characteristic p of the finite field
	"ExtensionDegree"	the extension degree d of the finite field over
	"FieldSize"	the number of elements q=p^d of the field
	"FieldIrreducible"	the polynomial function f used to construct the field
	"ElementRepresentation"	"Polynomial" or "Exponential"

Examples

open allclose all

Basic Examples (2)

Represent the prime field :

Do arithmetic:

Do polynomial algebra:

Represent a finite field with characteristic and extension degree :

Specify elements of the field using polynomial coefficients or an index:

Do arithmetic:

Do polynomial algebra:

Scope (13)

Representation and Properties (4)

Represent a finite field with characteristic and extension degree :

Find the irreducible polynomial used to construct the field:

By default, the polynomial representation of field elements is used:

Find other properties of the field:

Field additive and multiplicative identity elements have indices and :

Construct a finite field using a custom irreducible polynomial:

Verify that the polynomial is irreducible:

Represent the field:

The field irreducible is equal to the specified polynomial modulo the field characteristic:

Construct a finite field that uses exponential representation of elements:

The polynomial used to represent the field is primitive:

Field additive and multiplicative identity elements have indices and :

All nonzero elements of the field are powers of the element with index :

Represent a prime field:

Represent a finite field with 49 elements:

Arithmetic (3)

Perform arithmetic operations in a finite field:

Rational powers work only with exponent denominators and :

For some field elements, the square root may not exist:

Arithmetic operations treat integers as elements of the field:

Rational numbers need to be valid modulo the field characteristic:

Use Element to decide which rational numbers can be identified with field elements:

For the purpose of comparison, rational numbers are identified with field elements:

Elements of different finite fields cannot be combined:

Fields with same characteristic and field irreducible but different element representations are allowed:

Automorphisms and Embeddings (2)

Compute all conjugates of a finite field element:

The conjugates are roots of the minimal polynomial of a:

The Frobenius automorphism maps to :

Compute an embedding of one finite field in another:

Map finite field elements through the embedding:

Embeddings preserve arithmetic operations:

Polynomials over Finite Fields (2)

Compute with polynomials over a finite field:

Expand products:

Compute the GCD:

Cancel a fraction:

Compute quotient and remainder:

Factor a polynomial:

Compute a resultant:

Compute with multivariate polynomials:

Factor a polynomial over an extension of a finite field:

The polynomial is irreducible over :

Factor after embedding in a larger field :

Linear Algebra over Finite Fields (1)

Compute with matrices over a finite field:

Multiply matrices:

Compute a power of a matrix:

Compute the determinant:

Compute the inverse:

Solve linear equations:

Compute the rank and the null space of a matrix:

Compute the LU decomposition of a matrix:

Row reduce a matrix:

Find the characteristic polynomial of a matrix:

Equations over Finite Fields (1)

Solve equations over a finite field:

Univariate equations:

Systems of linear equations:

Systems of polynomial equations:

Find solution instances:

Eliminate quantifiers:

Applications (8)

Implement an error-correcting code. The Hamming code encodes a -bit message in an -bit sequence and is able to correct up to one error:

Let be a finite field with elements using the exponential element representation, let be the irreducible polynomial used to construct , and let be the generator of :

The encoded message is the coefficient list of , where the coefficient list of is the original message:

Let be the polynomial whose coefficient list is the received message:

If the received message contains no errors, then , and hence :

If the received message contains one error in position , then , and hence :

Check and correct the received message:

To decode the message, compute the coefficient list of :

The decoded message is correct when the received message has no errors or one error:

Construct orthogonal Latin squares of order for any prime power . A Latin square of order is a array such that each row and each column contains every element of a set of elements exactly once. A pair of Latin squares is said to be orthogonal if the pairs formed by juxtaposing the two arrays are all distinct:

Verify that all arrays are Latin squares:

Verify that all pairs of arrays are orthogonal:

A finite set of integers is a Sidon set if the sums for are all distinct. Construct a Sidon set of integers in , for a prime power :

Verify that is a Sidon set of length :

A de Bruijn sequence of order for an alphabet with letters is a cyclic sequence of letters of the alphabet, such that every sequence of letters appears exactly once as a subsequence of . Construct a de Bruijn sequence of order for an alphabet with letters, for a prime power :

Verify that is a de Bruijn sequence of order for an alphabet with letters:

An matrix is a Hadamard matrix if all entries of are or and $H.TemplateBox[{H}, Transpose]=n I_n$ . Construct a Hadamard matrix of order for any prime power with :

Implement the Rijndael S-box step used in the Advanced Encryption Standard (AES) algorithm. The first part, called the Nyberg S-box, uses multiplicative inverse in :

The second part involves an affine transformation over :

The forward S-box is the composition of the two parts:

Compute the forward S-box table in the hexadecimal notation:

Define the inverse S-box transformation:

Compute the inverse S-box table in the hexadecimal notation:

Verify that the inverse S-box is the inverse of the forward S-box:

Implement a Diffie–Hellman public key cryptosystem with a 2049-bit prime:

Find a primitive element of the field :

The first user chooses a private key :

The public key consists of , and :

The second user chooses :

To send a 2048-bit message , the second user sends and :

The first user can recover by computing :

Implement a digital signature scheme. Fix a prime and find a primitive element of :

Pick a secret integer and publish , and :

The signature for a message is a pair of positive integers less than such that . Computing the signature requires the knowledge of the secret integer :