Assume we have an odd integer n, a ring R with characteristic n, a unit u in this ring, and an integer s > sqrt(n) with the following property. For every prime q dividing s, us/q-1 is a unit in R, and us = 1. Furthermore, there is a polynomial p(x), of degree t, with integer coefficients, whose roots are u, un, un2, and so on up to unt-1. I know, this is asking a lot, but occasionally one can garner this much information, as in the mersenne prime test on the next page.
If n is prime, let R be the finite field of order nt. Let u be any primitive element raised to the (nt-1)/s power. Clearly us = 1, and u to any other power, minus 1, is nonzero, and hence a unit.
Build p(x) as described above. Let f be the frobenius automorphism, which raises everything to the nth power. Since f permutes the roots of p(x), f(p(x)) produces p(x). In other words, f fixes the coefficients of p(x). The n elements of R that satisfy xn = x are the integers 0 through n-1, hence the coefficients, fixed by f, are integers. The conditions of the nst prime test are met, for any exponent t.
If n is really prime, such a finite field is constructed quickly, albeit probabilistically. Find an irreducible polynomial of degree t over Zn in the indeterminant c. (Procedures for doing this were presented in an earlier section.) If you have trouble finding such an irreducible polynomial, then n is not prime. Go back to the strong pseudoprime test and try to prove n is composite.
Having created a ring that "looks" like a finite field of characteristic n, set u = c(nt-1)/s, and verify us = 1. (There is a good chance c is primitive.) Remember that u is a polynomial in c, with coefficients in Zn. If us is not 1, or if any of the following conditions fail, your polynomial may not be irreducible after all, or perhaps c is not primitive, or perhaps n is not prime. Go back and try again.
Next look at us/q-1. Multiplication by this element takes a polynomial in c to a polynomial in c, and acts as a ring endomorphism on R. Write this transformation as a matrix in Zn. The element is a unit iff the matrix is invertible, iff the determinant is a unit. Use gaussian elimination to find the determinant, and make sure it is invertible mod n.
Finally, built the polynomial with the prescribed roots. Make sure its coefficients are all integers.
Assume the nst conditions have been verified by computer, and continue the proof. Actually there is one more assumption, which is satisfied by the ring we have constructed. We need R to be a finitely generated Znmodule. Thus R is an integral extension of Zn, and if p prime divides n, the corresponding prime ideal in Zn can be lifted up to a maximal ideal in R. Mod out by this ideal, and the associated homomorphism h() maps R onto a finite field of characteristic p.
Let h(u) = v. Of course vs = 1, just as us = 1.
Remember that a unit cannot map to 0. Apply h to us/q-1 and find a nonzero element in a field, which is a unit. Thus vs/q-1 is a unit.
Since vs/q ≠ 1, v has order s in the field.
The polynomial whose roots are u, un, un2, etc, becomes a comparable polynomial in the powers of v, having integer coefficients. The frobenius automorphism fixes these integer coefficients, and permutes the roots. Remember that these roots are powers of v. When raising v to a power, it is sufficient to reduce the exponent mod s. The values of ni mod s, and there may be repeats here, must be permuted by the frobenius automorphism.
Raising to the p multiplies the exponent by p. Start at the first exponent, which is n0, or 1. Thus p = ni mod s for some i. Assume p is a prime below sqrt(n), hence p < s. Let i run from 1 to t-1, evaluate ni mod s, and see if this is a prime factor of n. That's t-1 trial divisions, and we're done. If we have found no prime factors, then n is prime.