FiniteFieldElement

gives the element of the finite field ff with index ind.

gives the element c₀+c₁θ+c₂θ²+… of the finite field ff, where θ is the field generator of ff.

Details

FiniteFieldElement is used to represent an element in a FiniteField.
FiniteFieldElement objects in the same field are automatically combined by arithmetic operations.
Information[a,prop] or a[prop] gives the property prop of the FiniteFieldElement object a. The following properties can be specified:

	"Field"	the ambient field ff of a
	"Index"	the index of a
	"Coefficients"	{c₀,c₁,c₂,…} where a=c₀+c₁θ+c₂θ²+…
	"Characteristic"	the characteristic p of ff
	"ExtensionDegree"	the extension degree d of ff over
	"FieldSize"	the number of elements of ff
	"FieldIrreducible"	the polynomial function f used to construct the field ff
	"ElementRepresentation"	"Polynomial" or "Exponential"

MinimalPolynomial[a,x] gives the minimal degree monic polynomial in that is zero at a.
MultiplicativeOrder gives the multiplicative order of nonzero finite field elements.
Polynomial operations such as PolynomialGCD, Factor, Expand, PolynomialQuotientRemainder and Resultant can be used for polynomials with finite field element coefficients. Together and Cancel can be used for rational functions with finite field element coefficients.
Linear algebra operations such as Det, Inverse, RowReduce, NullSpace, MatrixRank and LinearSolve can be used for matrices with finite field element entries.
Solve and Reduce can be used to solve systems of equations over finite fields.

Examples

open allclose all

Basic Examples (1)

Represent a finite field with characteristic and extension degree :

Specify an element of the field using polynomial coefficients:

Equivalent specification:

Specify an element of the field using an index:

Equivalent specification:

Do arithmetic:

Do polynomial algebra:

Finite field elements are atomic objects:

Extract properties of a finite field element:

Scope (13)

Representation and Properties (4)

Represent a finite field with characteristic and extension degree :

Specify an element of the field using polynomial coefficients:

Equivalent specification:

Finite field elements are atomic objects:

Extract the polynomial coefficients and the field from a finite field element:

Specify an element of the field using an index:

Equivalent specification:

Extract the index and the field from a finite field element:

Extract field properties from a finite field element:

Extract properties using Information:

Field additive and multiplicative identity elements have indices and :

Construct a finite field that uses exponential representation of elements:

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

Field additive and multiplicative identity elements have indices and :

Each element of can also be represented as a polynomial of degree in :

Large indices are typeset in a shortened format:

Large characteristics are typeset as symbolic p:

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 the 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:

A polynomial irreducible over factors 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 a 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 :