Algebra`FiniteFields`
A field is an algebraic structure obeying the rules of ordinary arithmetic. In particular, a field has binary operations of addition and multiplication, both of which are commutative and associative. A field has two special elements, the additive identity , and multiplicative identity . This package adds rules to Plus, Times, and Power so that arithmetic on field elements will be defined properly. It also provides lowlevel utilities for working with finite fields and for formatting finite field elements.
For any finite field there is a fixed prime number , called the characteristic of the field, such that the sum of of the field elements gives the field element. A finite field of characteristic has elements for some positive integer , which we will loosely call the extension degree. This package represents field elements as polynomials in a single variable. The polynomials have degree at most and their coefficients are integers reduced mod .
The internal form of a finite field element is GF[p, ilist][elist] where GF stands for Galois field, is the prime characteristic of the field, ilist is the coefficient list of the irreducible polynomial which defines multiplication in the field, and elist is the coefficient list of the polynomial representing the particular element. Because this form can be a bit clumsy, the package provides several shortcuts for entering finite field elements.
Ways to enter finite field elements.
This loads the package.
In[1]:= <<Algebra`FiniteFields`
Add 4 and 5 mod 7. The default output form is subscripted.
In[2]:= GF[7][{4}] + GF[7][{5}]
Out[2]=
Here is the FullForm of the expression. Note the automatic choice of irreducible polynomial.
In[3]:= FullForm[%]
Out[3]//FullForm=
Here is multiplication in the field of 3^4 == 81 elements.
In[4]:= GF[3,4][{1,2,1}] GF[3,4][{2,2,2,0}]
Out[4]=
Field objects are automatically reduced to a canonical form.
In[5]:= GF[3,4][{1,2,3,4,5}]
Out[5]=
Since Mathematica lists polynomials with the constant term first, the same is done for finite field elements. In this example, the lefthand zero is essential to give the constant term, but the righthand zero in the input is unnecessary.
In[6]:= GF[3,4][{0,1,0}]
Out[6]=
It is nonsense to add elements of different finite fields, so this expression does not evaluate.
In[7]:= GF[5,1][{1}] + GF[3,4][{1,1,1}]
Out[7]=
Integers are imported into finite fields.
In[8]:= 1 + GF[3,4][{1,1}]
Out[8]=
Zero is special. This package makes the assumption that zero is zero, regardless of the field it is in. The main consequence of this is that a field zero is simplified to the integer automatically. Many functions in Mathematica work better with this assumption. The assumption is not rigorously correct, but will not produce nonsensical output unless nonsensical input is given.
Field zeros are simplified to the integer after arithmetic.
In[9]:= {GF[7][{1}] + GF[7][{6}], GF[3,4][{0,0,0}]}
Out[9]=
The sum of the field zeros from different fields also simplifies to .
In[10]:= GF[7][{0}] + GF[3,4][{0,0,0}]
Out[10]=
Field element formatting.
One may always input or output the FullForm of a finite field element, however the package provides some shortcuts. The elements of a prime field may be written GF[p][k] or GF[p, 1][k], both of which are interpreted as GF[p, 0,1][k]. In general if with prime and a positive integer, then GF[s] is interpreted as GF[p, d]. The expression GF[3, 4] stands for a degree 4 extension of the integers mod 3, that is, a field with 81 elements. When this form is used, the package automatically selects an irreducible polynomial, with coefficients given by ilist and with the property that GF[p, ilist][0,1] is a primitive element of the field. It is possible to provide your own irreducible polynomial by giving it explicitly, as in GF[3, {1, 1, 1, 1, 2, 1}].
The default OutputForm of a finite field element is a list of integers subscripted by the characteristic of the field. The length of the list is the degree of the field extension over the prime field. If you are working with only one representation of any field, then this will be sufficient to distinguish which field contains a given element.
Since it is possible to have fields of the same size using different irreducible polynomials, it is useful to be able distinguish elements from these fields. It is also convenient to have a more compact way to type finite field elements. The function SetFieldFormat establishes the input and output formats of field elements. You may always input field elements in the ways already described, or ask explicitly for the FullForm of the output.
Note that a field head, such as GF[2, 3] may be assigned to a symbol. The assignment f8 = GF[2, 3] allows you to refer to a specific field element using f8[{1,0,1}].
Give a field with 9 elements a functional format.
In[11]:= SetFieldFormat[GF[9], FormatType > FunctionOfCoefficients[f9]]
Here is some arithmetic with elements from this field.
In[12]:= example = {f9[1,2] + f9[2], f9[1,2]^3, 2 f9[2], f9[2]/f9[2,2]}
Out[12]=
Represent each element as an integer in the range 0 to 8, rather than as a sequence of polynomial coefficients.
In[13]:= SetFieldFormat[GF[9], FormatType > FunctionOfCode[f9]]
Here the arithmetic results are encoded.
In[14]:= example
Out[14]=
This restores the default formatting for this field.
In[15]:= SetFieldFormat[GF[9]]
Field parameter functions.
The functions Characteristic, ExtensionDegree, FieldSize, FieldIrreducible, and IrreduciblePolynomial give important parameters about a finite field.
Characteristic gives the prime characteristic of the field.
In[16]:= (fld = GF[81]; Characteristic[fld])
Out[16]=
A field extension is a vector space over the base field. ExtensionDegree gives the dimension of this vector space.
In[17]:= ExtensionDegree[fld]
Out[17]=
FieldSize gives the number of elements in the field.
In[18]:= FieldSize[fld]
Out[18]=
Here is an identity.
In[19]:= FieldSize[fld] == Characteristic[fld]^ExtensionDegree[fld]
Out[19]=
This gives the irreducible polynomial associated with a field.
In[20]:= FieldIrreducible[fld, x]
Out[20]=
Field element manipulation functions.
The functions Successor, ReduceElement, ToElementCode, FromElementCode, PolynomialToElement, and ElementToPolynomial are for working with finite field elements.
This gives the element as a polynomial.
In[21]:= ElementToPolynomial[fld[{1,2,1,2}], x]
Out[21]=
Functions to support fast multiplication and division.
A finite field must have a prime power number of elements. If it has elements, where is a prime, then it is isomorphic to the integers mod . In this case the package does addition, subtraction, multiplication, and positive powers as usual over the integers and reduces the results using Mod. For negative powers the package uses PowerMod.
If the field has elements, where , then it is isomorphic to the set of polynomials in some variable having degree less than and with coefficients in the integers mod . Addition is polynomial addition except that the coefficients are reduced modulo . For multiplication the product is also reduced modulo an irreducible (nonfactorable) polynomial over the integers modulo .
Taking multiplicative inverses is equivalent to finding the extended greatest common divisor modulo with the irreducible polynomial. In other words, given the field element elem and the field's irreducible polynomial irred, find polynomials and such that PolynomialGCD[elem, irred, Modulus > p] equals PolynomialMod[a elem + b irred, p]. If the result of PolynomialGCD is unity, then is the inverse of elem.
There is a faster way to do multiplication and compute inverses, based on the fact that the multiplicative group of any finite field is cyclic. If you have a generator of the group along with a list of the positive powers of the generator in sequence, then multiplication and division can be reduced to adding and subtracting indices of the elements in the list.
The package supports this method of arithmetic by allowing you to either generate a field object from a list representing the powers of a primitive element (PowerListToField), or generate a list representing the powers of a primitive element from a field object (PowerList). Setting PowerListQ to True causes field arithmetic to use a list of primitive element powers, by defining the discrete exponential function FieldExp and the discrete logarithm function FieldInd. The FieldInd function is often called the index function for the field. The list of powers will depend on the choice of primitive element and on which irreducible polynomial is used for the field representation. Any element of the field for which FieldInd[elem] is relatively prime to FieldSize[f]1 is also a primitive element of the field.
Field arithmetic using a list of primitive element powers has two disadvantages. It takes time to enter or compute the list, and the list can take considerable memory. In general, if you are doing only a few arithmetic operations, or if you are working in a large field, it is better not to create the list. Note that setting PowerListQ to False disables this method of doing arithmetic in a particular field, but it does not destroy the computed values of FieldExp and FieldInd.
This shows that 3 is a primitive element of the integers mod 7. The other primitive element is 5. Since GF[7,1] is a prime field, it is inefficient to use a list of primitive element powers for multiplication.
In[22]:= PowerList[GF[7,1]]
Out[22]=
Although using a list of primitive element powers is an inefficient way to do GF[7,1] arithmetic, this enables the method anyway.
In[23]:= PowerListQ[GF[7,1]] = True
The position of {6} in PowerList is one greater than the index given by FieldInd.
In[24]:= FieldInd[GF[7,1][{6}]]
Out[24]=
FieldExp and FieldInd are inverses.
In[25]:= FieldExp[GF[7,1], 3]
Out[25]=
These definitions for field index and field exponent are not part of the conventional definitions, but may be useful in some applications.
In[26]:= {FieldInd[0], FieldExp[GF[7,1], Infinity]}
Out[26]=
Some books contain tables equivalent to the list given by PowerList. The function PowerListToField allows such a list to be used to define a field. The argument of PowerListToField is a list of tuples of integers. The first tuple is assumed to give the coefficients of the polynomial representation of the element of the field. This is used to determine whether the coefficients are listed constanttermfirst or constanttermlast. The second tuple is assumed to represent a primitive element of the field. The succeeding tuples are assumed to represent successive powers of the second element. PowerListToField does some elementary error checking to verify that the input list is valid. If so, PowerListToField computes parameters of the field such as the characteristic and the irreducible polynomial.
Here is a field of order 9.
In[27]:= g9 = PowerListToField[{{1, 0}, {0, 1}, {1, 2}, {2, 2}, {2, 0}, {0, 2}, {2, 1}, {1, 1}}]
Out[27]=
Arithmetic works on fields defined using PowerListToField.
In[28]:= {g9[{1}] + g9[{1,1}], g9[{1,2}] * g9[{2,2}], 1/g9[{0,2}], g9[{2,2}]^2}
Out[28]=
The field parameters are computed automatically.
In[29]:= {Characteristic[g9], ExtensionDegree[g9], FieldIrreducible[g9,z]}
Out[29]=
FieldExp may be used to generate the list of elements corresponding to the original list.
In[30]:= Table[FieldExp[g9, i], {i, 0, 7}]
Out[30]=
This gives the original list consisting of the data parts of the elements.
In[31]:= PowerList[g9]
Out[31]=
Compatibility with Other Mathematica Functions
Most Mathematica functions are not, indeed cannot be, designed to work over arbitrary fields. For instance, it is nonsensical to integrate an expression containing a finite field object. At best, such functions will not do anything when given such an expression.
You can generally expect these functions to treat the field object as an unknown symbol. Before using a function on an expression with finite field objects, it is wise to try some test cases first. The types of functions that might reasonably be expected to work are linear algebra and polynomial functions.
Set the format for GF[9].
In[32]:= SetFieldFormat[GF[9], FormatType > FunctionOfCode[f9]]
Fractional powers do not work.
In[33]:= Power[f9[1], 1/2]
Out[33]=
Factor fails because it makes the assumption that it is working over the rationals.
In[34]:= Factor[Expand[(x + f9[2])(x  f9[2])]]
Out[34]=
PolynomialGCD doesn't work either. Use PolynomialExtendedGCD defined in the package instead.
In[35]:= PolynomialGCD[x + f9[1], f9[2] x + f9[2]]
Out[35]=
Set the format for GF[3, 4].
In[36]:= SetFieldFormat[GF[3,4], FormatType > FunctionOfCoefficients[f81]]
PolynomialQuotient and PolynomialRemainder accept polynomials over a field.
In[37]:= {PolynomialQuotient[f81[2,2] x^4 + f81[1] x^2 + f81[1,1,1], f81[2] x^2 + f81[1,1,1,1], x], PolynomialRemainder[f81[2,2] x^4 + f81[1] x^2 + f81[1,1,1], f81[2] x^2 + f81[1,1,1,1], x]}
Out[37]=
PolynomialMod works on polynomials over the integers, not polynomials over a field. Also note that a polynomial over a field is not automatically sorted from lower power to higher power, because Mathematica does not treat GF objects as numbers.
In[38]:= PolynomialMod[f81[2,2] x^4 + f81[1] x^2 + f81[1,1,1], f81[2] x^2 + f81[1,1,1,1]]
Out[38]=
Det works on matrices of field elements.
In[39]:= (ffmatrix = {{f81[2,1,2], f81[1,1,1]}, {f81[1,2,1,2], f81[2]}}; Det[ffmatrix])
Out[39]=
RowReduce works except that the 1 should be in the field.
In[40]:= RowReduce[ffmatrix]
Out[40]=
Inverse and Dot also work with matrices of field elements.
In[41]:= Inverse[ffmatrix] . ffmatrix
Out[41]=
