Finite Fields and Their Applications

Adam Strzeboński, Wolfram Research

(RowDefault[, (Spacer1), , (Spacer1), ])  #WolframTechConf

ABSTRACT

Mathematica 13.3 contains new functionality for computation over finite fields, including finite field arithmetic, mappings, and polynomial computations. The upcoming version adds linear algebra and equation solving. In my talk I will present the new functionality and show some application examples.

Finite Fields

Representation

• FiniteField

• FiniteFieldElement

Element Operations

• Arithmetic (Plus, Times, integer Power)

• FiniteFieldElementTrace

• FiniteFieldElementNorm

• FiniteFieldElementPrimitiveQ

• MinimalPolynomial

• MultiplicativeOrder

Finite Field Mappings

• FrobeniusAutomorphism

• FiniteFieldEmbedding

Conversion Utilities

• ToFiniteField, FromFiniteField

• FiniteFieldIndex, FromFiniteFieldIndex

Polynomials over Finite Fields

PolynomialGCD, PolynomialLCM, PolynomialExtendedGCD, Expand, Factor, FactorList, FactorSquareFree, FactorSquareFreeList, IrreduciblePolynomialQ, PolynomialQuotientRemainder, PolynomialQuotient, PolynomialRemainder, Together, Cancel, Resultant, Discriminant

Linear Algebra over Finite Fields

Dot, MatrixPower, Det, Inverse, LUDecomposition, LinearSolve, RowReduce, NullSpace, MatrixRank, CharacteristicPolynomial

Equations over Finite Fields

Reduce, Solve, Resolve, FindInstance

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 the 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 (17^3) elements:

ff=FiniteField[17,3]

This gives the element with index 123:

a=ff[123]

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

Extract information about field and field elements:

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

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

a["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)):

c=ff[{3,5,7}]

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

Find the coefficients from the index:

Reverse[IntegerDigits[ind,17]]

“Exponential” Representation

This constructs a finite field with (23^4) elements in the “Exponential” representation:

ff=FiniteField[23,4,"Exponential"]

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:

θ=ff[{0,1}]

θ^123

θ^5+θ^7

Each element still can be represented as a polynomial in θ of degree at most d. Find the coefficients:

ff[1234]["Coefficients"]

%.θ^Range[0,3]

The "Exponential" representation provides somewhat faster finite field element arithmetic than the "Polynomial" representation, at the cost of a pre-computation 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)).

FiniteField[11,10,"Exponential"]

FiniteField[11,10]

Finite field Operations

ff=FiniteField[7,5]

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

Do arithmetic in the finite field:

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

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

a+3

Compute finite field element properties:

FiniteFieldElementTrace[a]

MinimalPolynomial[a,x]

MultiplicativeOrder[b]

Finite Field Mappings

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

ff=FiniteField[23,4]

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

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:

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

SameQ@@(MinimalPolynomial/@%)

Construct a larger field:

gg=FiniteField[23,12]

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

a+gg[123]

Construct an embedding of ff in gg:

emb=FiniteFieldEmbedding[ff,gg]

emb[a]

%+gg[123]

Embeddings preserve field operations:

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

Polynomials over Finite Fields

ff=FiniteField[19,3]

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

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

PolynomialRemainder[x^7-1,a x^3+b x+ a b,x]

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

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

Converting Coefficients

Convert polynomial coefficients to field elements:

ToFiniteField[x^3+21x+37,ff]

Factor[%]

Convert field elements to polynomials in t:

FromFiniteField[%,ff,t]

Collect[%,x]

ToFiniteField[%,ff,t]

Linear Algebra over Finite Fields

ff=FiniteField[79,3];

Convert a matrix of indices to a matrix of field elements.

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

(imat=Inverse[mat])//MatrixForm

mat.imat//MatrixForm

MatrixPower[mat,123456789]//MatrixForm

b=FromFiniteFieldIndex[RandomInteger[{0,79^3-1},{3}],ff]

a=LinearSolve[mat,b]

mat.a-b

Equations over Finite Fields

ff=FiniteField[11,5];

Solve[x^4+ff[123]x==ff[321],x]

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

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

FindInstance[ff[321]x^3+ff[432]y^3+ff[543]z^3==ff[654],{x,y,z}]

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

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

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

Find a primitive element of the field ff.

g=ff[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 ff, 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.

A finite set {1,2,…,(2^(n-1))} is a Sidon set in [1,(2^(n-1))].

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

q=49;
a=sidon[q]

Length[a]==q

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

Thank you for listening!