The theory of finite fields is a key part of number theory, abstract algebra, arithmetic algebraic geometry, and cryptography, among others. Many questions about the integers or the rational numbers can be translated into questions about the arithmetic in finite fields, which tends to be more tractable. As finite fields are well-suited to computer calculations, they are used in many modern cryptographic applications.
A field is a commutative ring in which every nonzero element has a multiplicative inverse.
That is, a field is a set with two operations, and , such that
(1) is an abelian group under addition;
(2) is an abelian group under multiplication, where is the additive identity in ;
(3) for all .
The rational numbers , the real numbers , and the complex numbers are all fields.
If is an algebraic integer, then is also a field.
The quotient ring is a field with elements. (This is sometimes written , but most textbooks reserve this notation for a different ring involving -adic integers.)
The last example is a finite field, with elements. From now on, it will be written and called "the field with elements." This requires some justification: why is there only one field with elements? To make sense of this, it is necessary to define a notion of when two fields are the same.
When two rings are isomorphic, they are essentially the same ring up to labelings of elements.
A homomorphism between two rings and is a function such that
An isomorphism is an homomorphism that is also a bijection. If there is an isomorphism between two rings, the rings are said to be isomorphic.
Here is a warmup that demonstrates some of the ideas involved in the classification of finite fields:
In a field , let be the smallest positive integer such that in . If does not exist, say that has characteristic , and if exists, say that has characteristic .
The characteristic helps classify finite fields:
If has characteristic , then is prime and there is a one-to-one homomorphism . In the latter case, if is finite, then it has elements for some positive integer .
The first step is to show that is prime. This is clear: suppose is not prime and write , . Then and since this is in a field, this implies that or , which violates the minimality of .
Next, define a homomorphism by ; this is clearly one-to-one and clearly a homomorphism. So there is a copy of inside .
The rest of the statement follows from the theory of vector spaces: is a vector space over , and since it is finite it has some dimension , and some basis , such that every element of can be written uniquely in the form for , so there are choices for elements of .
The above result is the first step in the classification of finite fields. This full classification is quite exact and quite strong. A partial proof will be given in the sections below.
(1) Every finite field has elements for some prime and some positive integer .
(2) For every prime and positive integer , there is a finite field with elements.
(3) Any two finite fields of the same size are isomorphic.
So: there is exactly one finite field with elements (up to isomorphism).
Note that (1) has been proved above. Proving (2) requires a quotient construction and an existence theorem about irreducible polynomials, and the proof of (3) follows quickly from the proof of (2).
As seen above, finite fields with elements contain a copy of . The construction of these fields starts with the polynomial ring of polynomials in one variable with coefficients in . The finite field with elements will be a suitable quotient of this ring.
The polynomial is irreducible in (in fact, it is the only irreducible quadratic polynomial in ). Consider the quotient Letting , can be thought of as where .
Then the elements of are . Polynomials in of larger degree can be reduced to linear polynomials in by using the relation . So has four elements, and in fact it is not hard to check that is a field. In particular, , so and are multiplicative inverses (and is its own inverse).
This field is denoted . Note that the characteristic of is . Do not mistake for the integers modulo : for example, is not a field, and in .
In general, if is a field, will be a field if and only if is irreducible. The proof is the same as the proof that is a field if and only if is prime: if is relatively prime with , there is a form of Bezout's identity that produces polynomials such that . Since all nonzero whose degree are less than that of are relatively prime to , because is irreducible, this gives multiplicative inverses for all the nonzero elements of
The number of elements in will be , where is the degree of , because every element of this field can be written uniquely as since all higher powers of can be reduced to lower powers via the relation .
So this construction gives a finite field of size for all primes and positive integers , if there is always an irreducible polynomial of any degree in . This is not immediately obvious.
Here is a fundamental fact that is essential in the proof of the classification theorem:
Let be a prime and a positive integer. Then, in ,
For example, in ,
The right side is the product of all the irreducible polynomials in of degree or .
Proof of the fact:
There are a few steps. First note that has no repeated factors: if it did, its derivative would share a common factor with it, but its derivative is just , which has no nontrivial factors.
Now, suppose is irreducible of degree . Then is a finite field of order . So if , in that field , by a generalization of Fermat's little theorem. This means that divides . If , , so divides hence divides .
The last step is to show that no other factors divide . This is best done by induction and using the fact that , but the details are omitted.
Taking the degrees of both sides gives a useful corollary:
For primes and positive integers , let be the number of monic irreducible polynomials of degree . Then
and by Möbius inversion,
It is not hard to see from the second formula that is always strictly greater than . (The term of the sum is strictly bigger than the sum of the absolute values of all the rest of the terms.) So there is always an irreducible polynomial in of degree , and hence a finite field of size .
Continuing the above example,
Let be the ring of polynomials with coefficients in . Recall that a polynomial is irreducible if it has no nonconstant factors of smaller degree.
For example, there are three irreducible polynomials of degree in , namely
How many irreducible polynomials of degree 17 are there in
Hint: read the finite fields wiki!
All that remains is to show that any two finite fields of the same size are isomorphic. So suppose is a finite field of size , and let where is irreducible of degree . To show that is isomorphic to , it suffices to show that there is a root of in . (Then there is a nontrivial homomorphism from defined by sending to the root, and any nontrivial homomorphism of fields is injective (why?), and any injective map between two sets of the same size is bijective.)
But consider the polynomial in ; by the generalization of Fermat's little theorem, this polynomial splits into linear factors over : and since , it must also split into linear factors over , so in fact it has distinct roots in .
The classification theorem implies that "the field with elements" exists and is well-defined (up to isomorphism).
The subfields of are easy to classify, given the above discussion. The interested reader is invited to supply a proof.
is a subfield of if and only if . In this case, consists of the elements satisfying .
Start with . Then there is a copy of inside . It consists of . It is straightforward to verify that these are the four roots of in .
One application of finite fields is in the construction of linear feedback shift registers, which are built from linear recurrence relations in The idea is that the sequence of solutions to a linear recurrence relation over a finite field is periodic, and the period is related to the characteristic polynomial of the recurrence, and to the arithmetic in the finite field where LFSRs are used in cryptography (to create pseudorandom number generators), circuit testing, digital communications, and many other areas.
In number theory, solutions to Diophantine equations are often analyzed by reducing the equations mod for prime Analysis of solutions to equations in is often easier than analysis over For instance, the structure of the points on a curve over is difficult to determine in general, but there are quite precise bounds on points over for curves with certain properties: if the number of points is then where is an easily computable number called the genus of the curve. These are the famous Hasse-Weil bounds, proved in 1974. Note that this implies that for all but finitely many i.e. there is a point.
The arithmetic of finite fields is used extensively in cryptographic applications, including elliptic curve public-key cryptography and the AES (Advanced Encryption Standard) for the encryption of electronic data, which uses the arithmetic in