Phoenix Finite Fields and Primitive Roots Technical Manual PDF

Chapter 11 Finite Fields and Primitive Roots 11.1 F p [ X ] In this chapter we will construct and study finite fields; an important tool will be the polynomial ring F p [ X ], where F p = Z /p Z is the finite field with p elements. We know that F p [ X ] is Euclidean, hence a PID and a UFD. When we regard Z /p Z as a finite field F p , we usually omit the “mod p Thus we simply write 1 = 2 in F 3 instead of 1 2 mod 3. This is standard practice don’t let this abuse of language confuse you. We know that the units in R = F p [ X ] are the nonzero constants: R Ч = F Ч p . This is because deg fg = deg f + deg g , so fg = 1 implies deg f = deg g = 0.

In particular, every polynomial f F p [ X ] is a unit times a monic polynomial. Since linear polynomials X + a for every a F p are irreducible ( X + a = fg implies 1 = deg f +deg g , hence f or g is a unit), they are primes. In particular, the polynomials X , X + 1, . . . , X + p 1 are primes in F p [ X ]. Are there more? Of course, if p = 2, then 2 X , 2 X + 1, . . . , 2 X + p 1 are also prime; but since e.g. 2 X + 1 = 2( X + 1 2 only by the unit 2, we regard them as one and the same prime (just as in Z , the primes 3 and 3 are counted as one). In order to minimize the confusion, let us agree that a prime is a monic polynomial (just as we can define a prime in Z to be positive).

A more satisfying solution would be to talk about prime ideals instead of primes: in Z we have (5) = ( 5), so 5 and 5 generate the same prime ideal (5), and in F p [ X ] we have ( X + r ) = ( aX + ar ) for all nonyero a . Now we will answer the question whether F p [ X ] contains infinitely many primes: 2 ) = 2( X + p +1 2 ) differs from X + p +1 Proposition 11.1. There are infinitely many primes in F p [ x ] . Proof. Assume that there are only finitely many, say f 1 = X , . . . , f r . Then let 96

Стр. 1

F = f 1 · · · f r + 1. Since deg F 1, this polynomial must have a prime factor f . Clearly f = f j since f j | F and f j | F 1 would imply that f j | 1. Thus f is a prime not on the list. In F 2 [ X ], the primes of degree 1 are X and X + 1. In order to find a new one, take F ( X ) = X ( X + 1) + 1 = X 2 + X + 1, which is irreducible in F 2 [ X ] and therefore a prime of degree 2. If you do the same thing in F 3 [ X ], then F ( X ) = X 2 + X + 1 is not irreducible since F ( X ) = ( X 1) 2 . but this gives you a new prime X 1 = X + 2.

Repeating Euclid’s argument gives F ( X ) = X ( X + 1)( X 1) + 1 = X 3 X + 1, which is irreducible (since it cannot be divisible by any linear factor) and therefore prime. Writing down primes explicitly is difficult. For example, f ( X ) = X 2 + 1 is prime in F 3 [ X ] but not in F 5 [ x ]. In fact: Proposition 11.2. Let p be an odd prime. Then X 2 + 1 is prime in F p [ X ] if and only if p 3 mod 4 . Proof. If p 1 mod 4, then there is some a F p with ar 2 = 1. Thus X 2 +1 = X 2 r 2 = ( X r )( X + r ) is reducible. Now assume that p 3 mod 4. If X 2 + 1 = ( X r )( X s ), then r + s = 0, hence X 2 + 1 = ( X r )( X + r ) = X 2 r 2 .

This implies r 2 = 1, which is impossible in F p for primes p 3 mod 4. This result should ring a bell: compare the factorizations of X 2 +1 in F p [ X ] with the factorizations of the principal ideal ( p ) in Q ( i ): p F p [ X ] Q ( i ) 2 X 2 + 1 = ( X + 1) 2 (2) = (1 + i ) 2 p 1 mod 4 X 2 + 1 = ( X r )( X + r ) ( p ) = ( a + bi )( a bi ) p 3 mod 4 X 2 + 1 = X 2 + 1 ( p ) = ( p ) This analogy will be explained in algebraic number theory. Thus it is not obvious that there exist primes of degree 2 in every F p [ X ]. In fact, such primes always exist: Proposition 11.3. There are exactly p ( p 1) 2 irreducible quadratic polynomials in F p [ X ] . Proof.

There are exactly p 2 monic polynomials X 2 + rX + s F p [ X ]. The reducible polynomials among them have the form ( X a )( X b ) for a, b F p . Recalling that ( X a )( X b ) = ( X b )( X a ) we easily see that there are exactly p 2 polynomials with a = b and p with a = b , hence there are p ( p +1) 2 reducible polynomials. Thus there exist exactly p ( p 1) 2 irreducible quadratic polynomials in F p [ X ]. 97

Стр. 2

For example, X 2 + X + 1 is the unique prime of degree 2 in F 2 [ X ], and the quadratic primes in F 3 [ X ] are X 2 + 1, X 2 + X 1 and X 2 X 1. This argument can be generalized to count the number of primes of any given degree. In this way, Gauss proved Proposition 11.4. For any prime p and any given n > 0 , there is an irreducible element f F p [ X ] of degree n . This is proved in abstract algebra. 11.2 Residue Classes modulo Polynomials Now recall that g h mod f if f | ( g h ). What can we say about the residue classes modulo f in F p [ X ]? Let us look at a few examples. 1. The ring F p [ X ] / ( X ) has exactly p residue classes 0 , 1, . . . , p 1:

in fact, since X 0 mod X we have a n X n + . . . + a 1 X + a 0 a 0 mod X . Thus every polynomial is congruent to a constant modulo X . On the other hand, a b mod X implies a = b , and the claim follows. The map sending the residue class a mod p to a mod X is a ring isomorphism: we have F p [ X ] / ( X ) F p . More generally, F p [ X ] / ( X a ) F p for any a F p . Make sure you understand why f ( X ) f ( a ) mod ( X a ). 2. The ring F p [ X ] / ( X 2 ) has exactly p 2 residue classes, namely a + bX with a, b F p . Note that this is not a field since X · X 0 mod X 2 . 3.

The ring F 2 [ X ] / ( f ) for f ( X ) = X 2 + X +1) has exactly 4 elements, namely the classes represented by 0, 1, X and X +1. For example, X 3 = X · X 2 X ( X 1) = X ( X + 1) = X 2 + X = X X 1 = 1 mod f . It is straightforward to compute an addition and multiplication table for the residue classes: + 0 1 X X + 1 0 0 1 X X + 1 1 1 0 X + 1 X X X X + 1 0 1 X + 1 X + 1 X 1 0 · 0 1 X X + 1 0 0 0 0 0 1 0 1 X X + 1 X 0 X X + 1 1 X + 1 0 X + 1 1 X 98

Стр. 3

In general, there are exactly N ( f ) = p deg f residue classes modulo f ; they form a ring denoted by F p [ X ] / ( f ). If you have a polynomial f ( X ) = X n + . . . + a 1 X + a 0 F p [ X ], then working modulo f works like this: observe that X n a n 1 X n 1 . . . a 1 X a 0 mod f allows you to reduce any polynomial g F p [ X ] to some polynomial of degree deg f by repeatedly applying this definition. For example, for f ( X ) = X 2 +1 we get X 2 1 mod f, X 3 X mod f, X 4 X 2 1 mod f etc. In particular, every polynomial g F p [ X ] is congruent modulo f to one of S f = { b n 1 X n 1 + . . . + b 1 X + b 0 : b j F p } . Moreover, none of the polynomials in S f are congruent modulo f :

if g i g j mod f for polynomials of degree deg f , then f | ( g i g j ), and since the polynomial on the right hand side has degree deg f , it must be 0. This shows that S f is a complete system of residue classes modulo f , and in particular it shows that there are exactly p deg f residue classes modulo f . Proposition 11.5. The ring F p [ X ] / ( f ) of residue classes modulo f has exactly p deg f elements. The norm of f is by definition N ( f ) = # F p [ X ] / ( f ) (this is how you define the norm of ideals in algebraic number theory), and we have found that N ( f ) = p deg f . 11.3 Finite Fields Now recall that if f is a prime in F p [ X ], then F p [ X ] / ( f ) is a domain:

in fact, if ab 0 mod f , then f | ab , hence f | a or f | b , which in turn implies that a 0 mod f or b 0 mod f . Since F p [ X ] / ( f ) has p deg f elements, it is a finite field. In abstract algebra you will see a proof that any finite field has p n elements for some prime p and some integer n 1, and that there is exactly one such field for each pair ( p, n ) up to isomorphism. Proposition 11.6. Let K be a field. Then every polynomial f K [ X ] has at most deg f roots. Proof. Assume that f has the root a K . Then f ( a ) = 0. Write f ( X ) = ( X a ) g ( X ) + r ( X ) for some polynomial r with deg r deg( X a ) = 1. Then deg r = 0, hence r ( X ) is a constant. Plugging in X = a shows that r = 0.

We have seen that if f ( a ) = 0, then f ( X ) = ( X a ) g ( X ) for some polynomial g of degree deg g = deg f 1. If g has a root, we can continue in this way; since after at most deg f steps we reach a constant polynomial, we see that we can 99

Стр. 4