A finite field (also called a Galois field) is a finite
algebraic structure where one can add, multiply and divide under the
same laws (for example, commutativity, associativity or
distributivity) as apply to the rational, real or complex numbers.
Unlike those three fields, for any finite field there exists a
positive prime integer , called the characteristic, such that
for any element in the finite field. In fact, the
number of elements in a finite field is a power of the characteristic
and for each prime and positive integer there exists exactly
one finite field with elements, up to isomorphism. For
more information about the algebraic structure and properties of
finite fields, see, for example,
S. Lang, Algebra, Second
Edition, New York: Addison-Wesley Publishing Company, Inc., 1984, ISBN
0 201 05487 6;
or
R. Lidl, H. Niederreiter, Finite Fields,
Encyclopedia of Mathematics and Its Applications, Vol. 20, Cambridge:
Cambridge Univ. Press, 1983, ISBN 0 521 30240 4.
When the field has elements and is called a prime field, discussed in the next section. There are several ways of implementing extensions of finite fields, and Axiom provides quite a bit of freedom to allow you to choose the one that is best for your application. Moreover, we provide operations for converting among the different representations of extensions and different extensions of a single field. Finally, note that you usually need to package-call operations from finite fields if the operations do not take as an argument an object of the field. See ugTypesPkgCall for more information on package-calling.
finite field Galois:field field:finite:prime field:prime field:Galois prime field modular arithmetic arithmetic:modular
Let be a positive integer. It is well known that you can get the same result if you perform addition, subtraction or multiplication of integers and then take the remainder on dividing by as if you had first done such remaindering on the operands, performed the arithmetic and then (if necessary) done remaindering again. This allows us to speak of arithmetic modulo or, more simply mod .
In Axiom, you use IntegerMod to do such arithmetic.
If is not prime, there is only a limited notion of reciprocals and division.
Here and are relatively prime, so has a multiplicative inverse modulo .
If we take to be a prime number , then taking inverses and, therefore, division are generally defined.
Use PrimeField instead of IntegerMod for prime.
You can also use and for the inverse of .
PrimeField (abbreviation PF) checks if its argument is prime when you try to use an operation from it. If you know the argument is prime (particularly if it is large), InnerPrimeField (abbreviation IPF) assumes the argument has already been verified to be prime. If you do use a number that is not prime, you will eventually get an error message, most likely a division by zero message. For computer science applications, the most important finite fields are PrimeField 2 and its extensions.
In the following examples, we work with the finite field with elements.
Like many domains in Axiom, finite fields provide an operation for returning a random element of the domain.
The element is a primitive element of this field, primitive element element:primitive
in the sense that its powers enumerate all nonzero elements.
If every nonzero element is a power of a primitive element, how do you determine what the exponent is? Use discrete logarithm discreteLog. logarithm:discrete
The order of a nonzero element is the smallest positive integer such .
The order of a primitive element is the defining .
finite field field:finite:extension of
When you want to work with an extension of a finite field in Axiom, you have three choices to make:
This illustrates one of the most important features of Axiom: you can choose exactly the right data-type and representation to suit your application best.
We first tell you what domain constructors to use for each case above, and then give some examples.
Constructors that automatically generate extensions of the prime field:
FiniteField
FiniteFieldCyclicGroup
FiniteFieldNormalBasis
Constructors that generate extensions of an arbitrary field:
FiniteFieldExtension
FiniteFieldExtensionByPolynomial
FiniteFieldCyclicGroupExtension
FiniteFieldCyclicGroupExtensionByPolynomial
FiniteFieldNormalBasisExtension
FiniteFieldNormalBasisExtensionByPolynomial
Constructors that use a cyclic group representation:
FiniteFieldCyclicGroup
FiniteFieldCyclicGroupExtension
FiniteFieldCyclicGroupExtensionByPolynomial
Constructors that use a normal basis representation:
FiniteFieldNormalBasis
FiniteFieldNormalBasisExtension
FiniteFieldNormalBasisExtensionByPolynomial
Constructors that use an irreducible modulus polynomial representation:
FiniteField
FiniteFieldExtension
FiniteFieldExtensionByPolynomial
Constructors that generate a polynomial for you:
FiniteField
FiniteFieldExtension
FiniteFieldCyclicGroup
FiniteFieldCyclicGroupExtension
FiniteFieldNormalBasis
FiniteFieldNormalBasisExtension
Constructors for which you provide a polynomial:
FiniteFieldExtensionByPolynomial
FiniteFieldCyclicGroupExtensionByPolynomial
FiniteFieldNormalBasisExtensionByPolynomial
These constructors are discussed in the following sections where we collect together descriptions of extension fields that have the same underlying representation.For more information on the implementation aspects of finite fields, see J. Grabmeier, A. Scheerhorn, Finite Fields in AXIOM, Technical Report, IBM Heidelberg Scientific Center, 1992.
If you don't really care about all this detail, just use FiniteField. As your knowledge of your application and its Axiom implementation grows, you can come back and choose an alternative constructor that may improve the efficiency of your code. Note that the exported operations are almost the same for all constructors of finite field extensions and include the operations exported by PrimeField.
All finite field extension constructors discussed in this finite field section field:finite:extension of use a representation that performs arithmetic with univariate (one-variable) polynomials modulo an irreducible polynomial. This polynomial may be given explicitly by you or automatically generated. The ground field may be the prime field or one you specify. See ugxProblemFiniteExtensionFinite for general information about finite field extensions.
For FiniteField (abbreviation FF) you provide a prime number and an extension degree . This degree can be 1.
Axiom uses the prime field PrimeField(p), here PrimeField 2, and it chooses an irreducible polynomial of degree , here 12, over the ground field.
The objects in the generated field extension are polynomials of degree at most with coefficients in the prime field. The polynomial indeterminate is automatically chosen by Axiom and is typically something like or . These (strange) variables are only for output display; there are several ways to construct elements of this field.
The operation index enumerates the elements of the field extension and accepts as argument the integers from 1 to .
The expression always gives the indeterminate.
You can build polynomials in and calculate in .
Among the available operations are norm and trace.
Since any nonzero element is a power of a primitive element, how do we discover what the exponent is?
The operation discreteLog calculates discrete logarithm the exponent and, logarithm:discrete if it is called with only one argument, always refers to the primitive element returned by primitiveElement.
FiniteFieldExtension (abbreviation FFX) is similar to FiniteField except that the ground-field for FiniteFieldExtension is arbitrary and chosen by you.
In case you select the prime field as ground field, there is essentially no difference between the constructed two finite field extensions.
FiniteFieldExtensionByPolynomial (abbreviation FFP) is similar to FiniteField and FiniteFieldExtension but is more general.
For FFP you choose both the ground field and the irreducible polynomial used in the representation. The degree of the extension is the degree of the polynomial.
finite field field:finite:extension of
In every finite field there exist elements whose powers are all the nonzero elements of the field. Such an element is called a primitive element.
In FiniteFieldCyclicGroup (abbreviation FFCG) group:cyclic the nonzero elements are represented by the powers of a fixed primitive element:primitive element primitive element of the field (that is, a generator of its cyclic multiplicative group). Multiplication (and hence exponentiation) using this representation is easy. To do addition, we consider our primitive element as the root of a primitive polynomial (an irreducible polynomial whose roots are all primitive). See ugxProblemFiniteUtility for examples of how to compute such a polynomial.
To use FiniteFieldCyclicGroup you provide a prime number and an extension degree.
Axiom uses the prime field, here PrimeField 3, as the ground field and it chooses a primitive polynomial of degree , here 4, over the prime field.
You can calculate in .
In this representation of finite fields the discrete logarithm of an element can be seen directly in its output form.
FiniteFieldCyclicGroupExtension (abbreviation FFCGX) is similar to FiniteFieldCyclicGroup except that the ground field for FiniteFieldCyclicGroupExtension is arbitrary and chosen by you. In case you select the prime field as ground field, there is essentially no difference between the constructed two finite field extensions.
FiniteFieldCyclicGroupExtensionByPolynomial (abbreviation FFCGP) is similar to FiniteFieldCyclicGroup and FiniteFieldCyclicGroupExtension but is more general. For FiniteFieldCyclicGroupExtensionByPolynomial you choose both the ground field and the irreducible polynomial used in the representation. The degree of the extension is the degree of the polynomial.
We use a utility operation to generate an irreducible primitive polynomial (see ugxProblemFiniteUtility ). The polynomial has one variable that is ``anonymous'': it displays as a question mark.
Let's look at a random element from this field.
finite field field:finite:extension of basis:normal normal basis
Let be a finite extension of degree of the finite field and let have elements. An element of is said to be normal over if the elements
form a basis of as a vector space over . Such a basis is called a normal basis.This agrees with the general definition of a normal basis because the distinct powers of the automorphism constitute the Galois group of .
If is normal over , its minimal polynomial:minimal polynomial is also said to be normal over . minimal polynomial There exist normal bases for all finite extensions of arbitrary finite fields.
In FiniteFieldNormalBasis (abbreviation FFNB), the elements of the finite field are represented by coordinate vectors with respect to a normal basis.
You provide a prime and an extension degree .
Axiom uses the prime field PrimeField(p), here PrimeField 3, and it chooses a normal polynomial of degree , here 8, over the ground field. The remainder class of the indeterminate is used as the normal element. The polynomial indeterminate is automatically chosen by Axiom and is typically something like or . These (strange) variables are only for output display; there are several ways to construct elements of this field. The output of the basis elements is something like
You can calculate in using .
FiniteFieldNormalBasisExtension (abbreviation FFNBX) is similar to FiniteFieldNormalBasis except that the groundfield for FiniteFieldNormalBasisExtension is arbitrary and chosen by you. In case you select the prime field as ground field, there is essentially no difference between the constructed two finite field extensions.
FiniteFieldNormalBasisExtensionByPolynomial (abbreviation FFNBP) is similar to FiniteFieldNormalBasis and FiniteFieldNormalBasisExtension but is more general. For FiniteFieldNormalBasisExtensionByPolynomial you choose both the ground field and the irreducible polynomial used in the representation. The degree of the extension is the degree of the polynomial.
We use a utility operation to generate an irreducible normal polynomial (see ugxProblemFiniteUtility ). The polynomial has one variable that is ``anonymous'': it displays as a question mark.
Let's look at a random element from this field.
Let be a finite field.
An extension field of degree over is a subfield of an extension field of degree over if and only if divides .
FiniteFieldHomomorphisms provides conversion operations between different extensions of one fixed finite ground field and between different representations of these finite fields.
Let's choose and ,
build the field extensions,
and pick two random elements from the smaller field.
Since divides , is a subfield of .
Therefore we can convert the elements of into elements of .
To check this, let's do some arithmetic.
There are also conversions available for the situation, when and are represented in different ways (see ugxProblemFiniteExtensionFinite ). For example let's choose where the representation is 0 plus the cyclic multiplicative group and with a normal basis representation.
Check the arithmetic again.
FiniteFieldPolynomialPackage (abbreviation FFPOLY) provides operations for generating, counting and testing polynomials over finite fields. Let's start with a couple of definitions:
In what follows, many of the generated polynomials have one ``anonymous'' variable. This indeterminate is displayed as a question mark (``?'').
To fix ideas, let's use the field with five elements for the first few examples.
You can generate irreducible polynomials of any (positive) degree polynomial:irreducible (within the storage capabilities of the computer and your ability to wait) by using createIrreduciblePolycreateIrreduciblePolyFiniteFieldPolynomialPackage.
Does this polynomial have other important properties? Use primitive? to test whether it is a primitive polynomial.
Use normal? to test whether it is a normal polynomial.
Note that this is actually a trivial case, because a normal polynomial of degree must have a nonzero term of degree . We will refer back to this later.
To get a primitive polynomial of degree 8 just issue this.
This polynomial is not normal,
but if you want a normal one simply write this.
This polynomial is not primitive!
This could have been seen directly, as the constant term is 1 here, which is not a primitive element up to the factor ( ) raised to the degree of the polynomial.Cf. Lidl, R. & Niederreiter, H., Finite Fields, Encycl. of Math. 20, (Addison-Wesley, 1983), p.90, Th. 3.18.
What about polynomials that are both primitive and normal? The existence of such a polynomial is by no means obvious. The existence of such polynomials is proved in Lenstra, H. W. & Schoof, R. J., Primitive Normal Bases for Finite Fields, Math. Comp. 48, 1987, pp. 217-231.
If you really need one use either createPrimitiveNormalPolycreatePrimitiveNormalPolyFiniteFieldPolynomialPackage or createNormalPrimitivePolycreateNormalPrimitivePolyFiniteFieldPolynomialPackage.
If you want to obtain additional polynomials of the various types above as given by the create... operations above, you can use the next... operations. For instance, nextIrreduciblePolynextIrreduciblePolyFiniteFieldPolynomialPackage yields the next monic irreducible polynomial with the same degree as the input polynomial. By ``next'' we mean ``next in a natural order using the terms and coefficients.'' This will become more clear in the following examples.
This is the field with five elements.
Our first example irreducible polynomial, say of degree 3, must be ``greater'' than this.
You can generate it by doing this.
Notice that this polynomial is not the same as the one createIrreduciblePolycreateIrreduciblePolyFiniteFieldPolynomialPackage.
You can step through all irreducible polynomials of degree 8 over the field with 5 elements by repeatedly issuing this.
You could also ask for the total number of these.
We hope that ``natural order'' on polynomials is now clear: first we compare the number of monomials of two polynomials (``more'' is ``greater''); then, if necessary, the degrees of these monomials (lexicographically), and lastly their coefficients (also lexicographically, and using the operation lookup if our field is not a prime field). Also note that we make both polynomials monic before looking at the coefficients: multiplying either polynomial by a nonzero constant produces the same result.
The package FiniteFieldPolynomialPackage also provides similar operations for primitive and normal polynomials. With the exception of the number of primitive normal polynomials; we're not aware of any known formula for this.
Take these,
and then we have:
What happened?
Well, for the ordering used in nextPrimitivePolynextPrimitivePolyFiniteFieldPolynomialPackage we use as first criterion a comparison of the constant terms of the polynomials. Analogously, in nextNormalPolynextNormalPolyFiniteFieldPolynomialPackage we first compare the monomials of degree 1 less than the degree of the polynomials (which is nonzero, by an earlier remark).
We don't have to restrict ourselves to prime fields.
Let's consider, say, a field with 16 elements.
We can apply any of the operations described above.
Axiom also provides operations for producing random polynomials of a given degree
or with degree between two given bounds.
FiniteFieldPolynomialPackage2 (abbreviation FFPOLY2) exports an operation rootOfIrreduciblePoly for finding one root of an irreducible polynomial polynomial:root of in an extension field of the coefficient field. The degree of the extension has to be a multiple of the degree of . It is not checked whether actually is irreducible.
To illustrate this operation, we fix a ground field
and then an extension field.
We construct an irreducible polynomial over .
We compute a root of .
and check the result