ermine the greatest common divisor in step (b). However, the first part of this calcula- tion may be difficult since the degree qd' may be a very large number. The solution to this problem is to note that the first step in Euclid's algorithm will be to evaluate - Z mod A(z). This can be done with the following routine. Evaluation of R(z) = z** - z mod A (z) (a) Ro(z) = z,e = 1. (b) Re(z) = [Re-1(z)]9 mod A(z). (c) If e < d, then [e e + 1, Go to (b)]. (d) R(z) = [Rd(z) - z] mod A(z). STOP. The degrees of the polynomials in the calculation never exceed qd, because of the judicious insertions of mod A(z) reductions into the calculations. The operation of raising a polynomial R(z) over GF(q) to the q-th power is a simple procedure as indicated in the following theorem. THEOREM 5A.10. Let R(z) be a polynomial over GF(q). Then (R(z)) = = (R(z4) (5A.45) Proof. Consider a polynomial R(z) with coefficients in the ground field GF(q), where q = pn, p being a prime number. (5A.46) If we raise R(z) to a power equal to the characteristic of the field GF(q) we (R(z)) (5A.47) Appendix 5A. Finite Field Arithmetic Here we have used the binomial expansion treating the d-th term as one element and the sum of the remaining terms as the other element in the expansion. The binomial coefficient (i) counts the number of times a term appears and, hence, can be considered to be the element of GF(q) corre- sponding to the sum of (i) unit elements. In GF(q), integer elements are added mod p. Since p is prime, (i) is divisible by p unless j = p or j = 0. Hence, (5A.48) Thus, (5A.49) and iterating this result on the remaining polynomial of degree (d - 1)p gives (5A.50) If this procedure is repeated n times we have (5A.51) Now a is in GF(q) where q = pn. Hence, the order of a divides q - 1 and aq = a. Therefore, (5A.52) This theorem makes the computation of R(z) equivalent to simply chang- ing the powers of Z in the polynomial. Hence, the evaluation algorithm for - Z mod A(z) is extremely efficient numerically. Highly structured sieve methods w