New in Version 14

Finite Fields and Their Applications

Finite Fields

Representation

FiniteField

FiniteFieldElement

Element Operations

Arithmetic (Plus, Times, Power with an integer exponent)

FiniteFieldElementTrace

FiniteFieldElementNorm

FiniteFieldElementPrimitiveQ

MinimalPolynomial

MultiplicativeOrder

Finite Field Mappings

FrobeniusAutomorphism

FiniteFieldEmbedding

Conversion Utilities

ToFiniteField, FromFiniteField

FiniteFieldIndex, FromFiniteFieldIndex

Polynomials over Finite Fields

PolynomialGCD, PolynomialLCM, PolynomialExtendedGCD

Factor, FactorList, FactorSquareFree, FactorSquareFreeList, IrreduciblePolynomialQ

Expand, Together, Cancel

PolynomialQuotientRemainder, PolynomialQuotient, PolynomialRemainder

Resultant, Discriminant

Linear Algebra over Finite Fields

Dot, MatrixPower

Det, CharacteristicPolynomial

Inverse, LinearSolve, LUDecomposition

RowReduce, NullSpace, MatrixRank

Equations over Finite Fields

Solve

FindInstance

Reduce

Resolve

Finite Field Representation

A finite field ff is represented by FiniteField[p,f,rep], where p is a prime number, f is a polynomial function irreducible over (Subscript[ℤ, p]), and rep is "Polynomial" or "Exponential" . p is called the characteristic of ff, f is called the field irreducible of ff, and the degree d of f is called the extension degree of ff over (Subscript[ℤ, p]). ff has (p^d) elements indexed by integers between 0 and (p^d)-1.

This constructs a finite field with (7^5) elements:

ff=FiniteField[7,5]

This gives the element with index 12345:

a=ff[12345]

Field elements are represented by atomic FiniteFieldElement objects:

{Head[a],AtomQ[a]}

Elements of ff can be expressed as polynomials of degree at most d-1 in the field generator θ, where f(θ)=0. This specifies a field element through a coefficient list of a polynomial in θ:

b=ff[{1,2,3,4,5}]

Extract information about field and field elements:

Information[ff,{"Characteristic","FieldIrreducible","FieldSize"}]

Information[a,{"Index","Coefficients","Field"}]

b["Index"]

“Polynomial” Representation

In the default "Polynomial" representation, the index of the field element c=(Subscript[c, 0])+(Subscript[c, 1])θ+⋯+(Subscript[c, d-1])(θ^(d-1)) is ind=(Subscript[c, 0])+(Subscript[c, 1])p+⋯+(Subscript[c, d-1])(p^(d-1)).

Construct the field element with the specified coefficients between 0 and p-1:

c=ff[{5,4,3,2,1}]

Compute the index from the coefficients:

ind = {5,4,3,2,1}.(7^Range[0,4])

Find the coefficients from the index:

Reverse[IntegerDigits[ind,7]]

“Exponential” Representation

In the "Exponential" representation, the field irreducible is chosen to be a primitive polynomial, and hence each nonzero element of the field is a power of the field generator. The index of the field element (θ^k), 0≤k≤(p^d)-2, is k+1. The index of the field zero is 0.

The "Exponential" representation provides somewhat faster finite field element arithmetic than the "Polynomial" representation, at the cost of a precomputation necessary when the field is created. The precomputed table has size proportional to the number of field elements, hence the "Exponential" representation can be used only for relatively small fields ((p^d)≤(10^9)).

Construct a finite field with (19^3) elements in the "Exponential" representation:

ffe=FiniteField[19,3,"Exponential"]

Compute the field generator θ using the coefficient specification θ=0*(θ^0)+1*(θ^1):

θ=ffe[{0,1}]

The index of (θ^k) is k+1:

θ^123

Add two powers of θ:

a=θ^5+θ^7

Each field element still can be represented as a polynomial in θ of degree at most d.

Find the coefficients of a:

cfa=a["Coefficients"]

Verify correctness of the coefficients:

cfa.θ^Range[0,2]==a

Operations on Field Elements

Do arithmetic in the finite field:

{a,b} ={ff[123],ff[456]}

(a^2+3b)/(a b^3-5)

Integers and rational numbers valid mod p are automatically treated as field elements:

a+3

Compute finite field element properties:

FiniteFieldElementNorm[a]

MinimalPolynomial[a,x]

MultiplicativeOrder[b]

Finite Field Mappings

The Frobenius automorphism is given by ϕ:f f∋a⟶(a^p)∈f f. All automorphisms of f f are functional powers of the Frobenius automorphism (the first d powers are different).

Automorphisms preserve field operations:

FrobeniusAutomorphism[a]+FrobeniusAutomorphism[b]==FrobeniusAutomorphism[a+b]

FrobeniusAutomorphism[a] FrobeniusAutomorphism[b]==FrobeniusAutomorphism[a b]

Find all conjugates of a field element:

conj=Table[FrobeniusAutomorphism[a,k],{k,0,4}]

All conjugates have the same minimal polynomial as a:

Table[MinimalPolynomial[c]===MinimalPolynomial[a],{c,conj}]

Construct a finite field with (7^15) elements:

gg=FiniteField[7,15]

Adding an element of ff to an element of gg is not defined:

a+gg[123]

ff is isomorphic to a subfield of gg, but is not automatically considered a subfield of gg, because there is no “standard” embedding of ff in gg.

Construct an embedding of ff in gg:

emb=FiniteFieldEmbedding[ff,gg]

Map a through the embedding:

aa=emb[a]

The result can be added to an element of gg:

aa+gg[123]

Embeddings preserve field operations:

{emb[a]+emb[b]==emb[a+b], emb[a] emb[b]==emb[a b]}

Polynomials over Finite Fields

Factor a polynomial over ff:

Factor[x^3+2x+5,Extension->ff]

Compute with polynomials whose coefficients belong to ff:

{q,r}=PolynomialQuotientRemainder[x^5-a^2,a x^2+b x+ a b,x]

Expand[q*(a x^2+b x+ a b)+r-(x^5-a^2)]

Discriminant[a x^3+a^2 x^2y^2 +b^3x+5a y,x]

Cancel[(x-a)/MinimalPolynomial[a, x]]

Converting Coefficients

Functions ToFiniteField and FromFiniteField can be used for converting between polynomials with finite field coefficients and polynomials with integer coefficients.

Convert polynomial coefficients to field elements:

poly=ToFiniteField[x^5+5x+2,ff]

Factor the result:

facs=Factor[poly]

Convert finite field element coefficients to polynomials in t, where t represents the field generator:

tfacs=FromFiniteField[facs,ff,t]

Collect coefficients at powers of x:

tpoly=Collect[tfacs,x]

Convert polynomials in t to field elements:

ToFiniteField[tpoly,ff,t]

Linear Algebra over Finite Fields

Generate a random matrix of finite field elements by converting a randomly generated matrix of indices:

(mat=FromFiniteFieldIndex[RandomInteger[{0,7^5-1},{3,3}],ff])//MatrixForm

Compute a power of mat:

MatrixPower[mat,123456789]//MatrixForm

Compute the determinant of mat:

Det[mat]

Compute the inverse of mat:

(imat=Inverse[mat])//MatrixForm

mat.imat//MatrixForm

Equations over Finite Fields

Solve univariate equations over a finite field:

Solve[x^3+a x==b,x]

Reduce[x^5+2x+5==0,x,ff]

Solve systems of equations and inequations over a finite field:

Solve[ff[11]x^2+ff[22]y^2==ff[33]&&ff[21]x^5+ff[43]y^5==ff[65],{x,y}]

FindInstance[x^3+y^3==z^3&&x y z!=0,{x,y,z},ff]

Applications

Finite fields are used in algebraic computation, error-correcting codes, cryptography, combinatorics, algebraic geometry, number theory and finite geometry.

Diffie–Hellman Public-Key Cryptosystem

Construct a public-key cryptosystem that allows you to send encrypted messages in 128-bit parts.

Find a prime field with a 128-bit characteristic:

p=NextPrime[2^128];
pf=FiniteField[p]

Find a primitive element of the field pf:

g=pf[PrimitiveRoot[p]]

The first user chooses a private key 2≤a≤p-2:

SeedRandom[1234];a=RandomInteger[{2,p-2}]

The public key consists of pf, g and (Subscript[g, 1])=(g^a):

g1=g^a

The second user chooses 2≤b≤p-2:

b=RandomInteger[{2,p-2}]

To send a 128-bit message m, the second user sends e=m (Subscript[g, 1]^b) and (Subscript[g, 2])=(g^b):

m=RandomInteger[{1,2^128-1}]

e=m g1^b

g2=g^b

The first user can recover m by computing e/(Subscript[g, 2]^a):

d=e/g2^a

d["Index"]==m

Sidon Sets

A finite set {(Subscript[a, 1]),…,(Subscript[a, n])} of integers is a Sidon set if the sums (Subscript[a, i])+(Subscript[a, j]) for 1≤i≤j≤n are all distinct. Sidon sets involving arbitrarily large integers are easy to construct. The finite set {1,2,…,(2^(n-1))} is a Sidon set in [1,(2^(n-1))]; however, the size of the integers involved is exponential in the size of the Sidon set. Using finite fields, we can construct Sidon sets with the size of integers involved quadratic in the size of the Sidon set.

Construct a Sidon set of q integers in [1,(q^2)-1], for a prime power q:

sidon[q_]:=
Module[{ff,g},
ff=FiniteField[q^2,"Exponential"];
g=ff[2];
(* Exponents k such that g^k-g belongs to the q-element subfield of ff *)Prepend[Select[Range[q^2-1],Mod[(g^#-g)["Index"]-1,q+1]==0&],1]]

Construct a Sidon set for q=49:

q=49;
ss=sidon[q]

Verify that ss is a Sidon set with q elements:

Length[ss]==q

sums=Join@@Table[ss[[i]]+ss[[j]],{j,q},{i,j}];
Length[sums]==Length[Union[sums]]==q(q+1)/2