Let F be a finite field of order pn, over the base field K of order pr. Remember that r divides n. Let d = n/r. In other words, F is a d dimensional extension of K, and if F = K(u), u is the root of a d dimensional monic irreducible polynomial over K.
How many primitive elements u lie in F? We're going to undercount them, which will give a "worst case" answer. If u generates F it is not in any subfield of F. The subfields of a finite field form an ascending chain, so we only need consider the largest proper subfield. The number of elements in F, and not in a smaller subfield, is at least pn-pn-1.
Each element u that spans F is a root of an irreducible polynomial of degree d in K. The conjugates of this root are all distinct, hence the elements that generate F can be partitioned into sets of size d. The number of irreducible polynomials of degree d, with coefficients in K, is at least (pn-pn-1)/d.
The total number of monic polynomials is pr raised to the d, or pn. Choose a polynomial at random, and it is irreducible with probability (1-1/p)/d. This is at least 1/2d, and usually closer to 1/d.
If we are interested in performing calculations in a finite field, and we need an irreducible polynomial to represent the elements, we only need select d of them before we are likely to find one, assuming there is an efficient test for irreduceability.
The reducible cubics are the irreducible quadratics times the linears (p3/2) plus the polynomials that split fully (p3/6), leaving p3/3 irreducibles.
Quartic reducibles are p×p3/3 + (p2/2)2/2 + (p2/2)×p2/2 + p4/24. This leaves p4/4 as expected.
The pseudoprime test is easily adapted for irreducibility. Let u = pd-1. Select a candidate polynomial w(x) at random and evaluate xu mod w. If w is irreducible the result is always 1. Turn this around, and xu ≠ 1 implies w is reducible. If w is irreducible, you can raise other polynomials to the u mod w and they should also produce 1.
If u has been factored, it is easy to prove that w is irreducible. The ring has pd elements. If w is reducible, some of these elements will be zero divisors. In contrast, if w is irreducible, all the nonzero elements will be units. If xu = 1, and xu/q is not 1 for every q dividing u, then the order of x is u. Everything other than 0 is a unit, and w is irreducible.
This is definitely worth doing, since false 1's are not uncommon. Let d = 4 and let w be the product of two different irreducible quadratics q(x) and r(x). Note that p2-1 divides evenly into p4-1. Looking mod q, xu = 1. The same is true mod r, and by the chinese remainder theorem, xu = 1, even though w is reducible. Choose any other polynomial not divisible by q or r, and the same thing is going to happen. This is the polynomial analogy of a carmichael number. I'll call it a carmichael polynomial.
Unfortunately the efficiency of this algorithm is 1/2, rather than 3/4. The "integer" proof carries over, except for one point where it breaks down. The next few paragraphs analyze this algorithm in detail, assuming you are familiar with the integer counterpart; but there is a better approach, that is faster (for modest degrees), so you may simply want to skip ahead.
Start by looking at the group of units in our ring. If q is an irreducible polynomial over a finite field F, look at the units in the ring F[x]/qm. Let c be a candidate polynomial that might be a unit. Multiplication by c carries 1 to c, x to cx, x2 to cx2, and so on. This is an F linear map that can be described by a matrix. The matrix is invertible iff c is a unit, iff det(c) is a unit. Every nonzero element of F is a unit, so c is either a unit or a zero divisor. By unique factorization of polynomials over F, c is a zero divisor iff it is divisible by q. Therefore the nonunits are the multiples of q, and the units are everything else.
If F[x]/q has order pd, there are pd×(m-1)×(pd-1) units. The two factors are coprime, and they represent the order of two disjoint subgroups in the group of units. If b is a generator of the units in F[x]/q, the powers of b, when reduced mod q, generate a cycle of length pd-1. Therefore the second subgroup of units is cyclic with order pd-1, and is generated by b plus some multiple of q(x). At this point the result looks very much like the units mod a prime power, but don't carry the analogy too far. That group is entirely cyclic, and this one is not. Consider the subgroup of units that are 1 mod qm-1. The product of 1+g(x) and 1+h(x) is now 1+g(x)+h(x). This group is isomorphic to Zpd, and is certainly not cyclic. Still, we know the group of units is a cycle of order pd-1, crossed with a p group, and that's all we need for now.
Now we are ready to look at the efficiency of the strong pseudoprime test for polynomials. At one point in the proof, the composite number is split into its prime powers. By analogy, w is split into irreducible polynomials raised to various powers. By the chinese remainder theorem, the units of our ring can be characterized by looking at the units under qm, where q is an irreducible factor of w. We just described these units above.
Recall the construction of the groups G and H. Since G has a primitive root of order 2×2k, and since this number is coprime to p, the same is true mod q. Now each q can contribute a 2k root of 1 or -1, in all combinations, leading to 2s square roots of 1.
If s is greater than 1 we have a ratio of 1/2, so assume s = 1, giving a prime power, like qm. The even roots of 1 live in the second cycle. The index is the size of the p-group. This could be as small as p, which could be as small as 3, but that still gives a ratio of 2/3.
Why can't we get away with 3/4? Recall the case where w is a carmichael polynomial. If p is large, the odds of either quadratic dividing into a random polynomial are near 0. So each polynomial is a unit, which becomes 1 when raised to the p2-1. The value of k reflects the factors of 2 in (p2-1)/2. Every unit, raised to the 2×2k, becomes 1. Every unit belongs to H, and the algorithm proves w is reducible with probability 1/2.
In summary, the strong pseudoprime test proves w is reducible (assuming it is reducible) with probability 1/2. Run it 20 times to gain a confidence of 1 in a million.
If q(x) is irreducible, of degree k, it extends the base field up to a larger finite field. The root x generates the entire field, not a subfield thereof.
If b is a primitive root, the order of b is pk-1. Write x as bj, and j cannot be a multiple of (pk-1)/(pd-1), where d divides k, else x would then be part of a smaller subfield. However, x need not be primitive either. In other words, j need not be coprime to pk-1. See finite fields for more details.
Consider the polynomial r(x) = xpk-1-1. Let b be primitive in the extension of dimension k. Note that b, and all the powers of b, satisfy r(x). These are distinct roots, and the number of roots equals the degree of r. We have found all the roots of r. Split r in this finite field, then group the linear factors back together to build irreducible polynomials mod p. Each polynomial implies a subfield, and has a degree d dividing k. Conversely, any irreducible polynomial q, with degree d dividing k, generates a finite field isomorphic to a subfield of our extension. The roots of q are also roots of r, hence q divides r. In summary, the factors of r are all the irreducible polynomials of degree d, where d divides k.
Since the formal derivative r′ is a pure power of x, none of these factors is repeated. Thus each irreducible polynomial appears only once.
One can adjust this result by changing the exponent on x. Instead of pk-1, use (pk-1)/c. This produces a factor of the aforementioned polynomial r(x), containing some, but not all of the irreducible chunks. If q is one of these chunks, its root, call it x, will have order (pk-1)/c.
To illustrate, let c = 2. The elements that are nonsquares in the finite field are left on the cuttingroom floor. This effectively separates the irreducibles of degree k by squares and nonswquares. Had we chosen another value of c, such as c = 3, the adjusted polynomial contains irreducibles whose roots are cubes in the finite field, leaving the noncubes behind. We'll see how this is used later on.
If w has degree 1 it is irreducible.
Let l(x) = xp-1-1. Apply the previous lemma, and l(x) contains every linear factor x-c, where c is nonzero mod p. (You can show the same thing by fermat's little theorem.) If w has a linear factor, we can find it easily by running gcd(w,l). In fact, you can reduce intermediate polynomials mod w(x) as you compute l(x). This can save time if p is large. In any case, we can quickly determine whether w has any linear factors, and if it does, it is reducible.
Having passed the linear test, suppose w is divisible by an irreducible polynomial q(x) of degree k. Let r(x) = xpk-1-1, and run gcd(w,r). This will extract any factors of degree k. If you get a gcd, w is reducible. Otherwise, try a larger k.
Run this test from k = 1 (the linear factors) to k = d/2. This determines, unambiguously, whether w is irreducible.
It is sometimes faster to jump straight from k = 1 to k = d/4+1. Suppose there are no factors between d/4+1 and d/2, yet w is divisible by q, where the degree of q is k, for k between 2 and d/4. Some multiple of k winds up in the range (d/4,d/2]. Say it is 3k. Build r(x) based on 3k. The lemma tells us that q divides r. Running gcd(w,r) will indeed extract the common factor q, and prove w is reducible.
Review the theory of formal derivatives. If the derivative w′ is 0 then every exponent on w is a multiple of p. This makes w a pth power of another polynomial. Cut the exponents down to size and factor the smaller polynomial, then raise the resulting primes to the p power. With this trick behind us, we will assume w′ is nonzero.
Recall that the gcd of w and w′ is divisible by qk iff w is divisible by qk+1. Use this to extract all the primes of w with multiplicity greater than 1. Call this polynomial y, and evaluate gcd(y,y′). This extracts all the primes of w with multiplicity greater than 2. Repeat this process until the gcd is a unit. At this point the polynomial y contains the primes of w that occur with the highest multiplicity. Each prime appears only once in y. Divide y into w as often as possible, giving a multiplicity m. Factor y, and raise each prime to the m. Then factor w/ym. This too may have repeated prime factors, with multiplicity less than m. These will be revealed by gcd(w,w′). Repeat this process until there are no repeated prime factors. Thus the problem has been reduced to factoring polynomials where each prime appears only once.
Apply the irreducibility test described above, letting k run from 1 to d/2. This extracts the linear factors, the quadratic factors, the cubic factors, and so on for each degree. thus the problem has been reduced to factoring w, where w consists of distinct primes, each having degree k.
The next trick is to split the primes of w by squares and nonsquares. Raise x to the (pk-1)/2, subtract 1, and take the gcd with w. This pulls out the prime factors whose roots are squares in their finite fields, and leaves the nonsquares behind. If we get w back again, if all the primes turn x into a square, we could try (pk-1)/c for some other value of c. But if c is large, you probably won't get anywhere. The odds of being a c power become small, and you'll probably leave all the primes behind. Here is another strategy that is more helpful.
Assume w consists of two or more primes of degree k that are all squares, or all nonsquares. Shift the roots by replacing x with x+1. Each root becomes a square or nonsquare, almost at random. If w splits, replace x with x-1 to find the corresponding factors in the original polynomial. If w still doesn't split, shift the roots again, and repeat.
I have implemented this algorithm, and it seems to work quite well. In theory it could run into trouble, especially for small moduli such as p = 3. There are only 3 chances to split w by squares and nonsquares. I could probably come up with a pathological polynomial over Z3 that won't factor via this algorithm, but I have no incentive to do so.
You probably noticed that p has to be odd. If p = 2, and k = 7, then pk-1 is prime, and there is no way to split w by squares, or cubes, or anything else.