Pomerance and Bleichenbacher: Constructing Finite Fields

Consider the following problem: Given a prime and an integer , find an irreducible polynomial of degree . And do so in time polynomial in and . There is a randomized algorithm which attacks this problem by picking a polynomial at random (approximately out of every polynomials will be irreducible), and testing each for irreducibility (which is fast), continuing this procedure until you find one, then stop. But we are interested here in a deterministic algorithm. Already for , this is a difficult problem, equivalent to finding a quadratic nonresidue modulo .

Assuming the ERH, Adleman and Lenstra have a solution to this problem. Unconditionally, they also find an irreducible polynomial of degree with , where is an effectively computable number. Letting and (where you do not know a priori if is prime), the polynomial produced has degree , and the runtime of the AKS algorithm becomes . We improve this theorem to the following:

Theorem. Such a polynomial can be produced with for sufficiently large and .

The bound for the sufficiently large' part depends effectively on the choice of .

Theorem. There is an effectively computable function and a deterministic algorithm such that if , , and , the algorithm produces pairs such that for each , is prime, , , the order of modulo is . Further, the are pairwise coprime, and . This algorithm runs in time .

Let be the Gaussian period of degree in (the trace of into the unique subfield of degree over ). The element has degree over the rationals (by coprimality). If is prime, and if is the minimal polynomial of then is irreducible over . Checking if in (together with some other conditions), we see that gives rise to a pseudofield.

Let . Throughout, we assume that is sufficiently large' with the bound being effectively computable, depending only on the choice of .

Proposition. All but primes have a prime with and the order of modulo is equal to .

Therefore up to , almost all of the primes are useful in the context of our theorem. This proposition is a natural extension of the argument in the original AKS paper, together with an added ingredient about the distribution of primes such that is smooth due to Pomerance and Shperlinski.

Proposition. Let be a set of primes with and . Then there are primes such that is free of primes from .

This proposition follows from a method of Balog, together with some effective estimates on the distribution of primes in residue classes. Together, these two propositions give the corollary:

Corollary. Let be the set of primes in the first proposition satisfying . Then

Proof. If this inequality did not hold, then by the first and second propositions, there must be primes having the properties of both propositions. By the first proposition, has a prime factor and the order of modulo is equal to . By one of the properties in the second proposition, . Then . This contradicts the second proposition.

Proposition. There exists a subset of in the corollary with product in the interval .

The proof of this theorem relies upon combinatorial number theory (essentially, you can solve a bin packing problem using the primes ). It relies upon:

Theorem. [Continuous Frobenius theorem] If is an open subset of , is closed under addition, and , then for any , , the measure of is , i.e.

where is the characteristic function of .

Now a remark about effectivity. It was proven by de la Vallée Poussin in 1896 that

as . The Siegel-Walfisz theorem states that this is true for for any fixed . This theorem is inherently ineffective because it depends on the existence or nonexistence of Siegel zeros. The Siegel-Walfisz theorem is ubiquitous in analytic number theory, being used in the Bombieri-Vinogradov theorem, Fouvry's theorem, and much else. The analytic number theory we use is an effective version of the Bombieri-Vinogradov theorem that does not rely on the Siegel-Walfisz theorem, and we replace the Fouvry theorem by a (weaker) result of Deshouillers-Iwaniec.

Now we give an outline of the proof of the Frobenius theorem. First, it is sufficient to prove the case where (i.e. contains only finitely many intervals). Second, since , for all either or (*). Now fix such that and consider all sets satisfying (**) as well as condition (*). Under these conditions, there exists a maximum to . We may thus assume that is a maximum. We show in the paper that we can assume that .

Let with . Let . For all and ,

This is trivial if , and otherwise, which implies

and therefore by assumption (*)

Let such that for all . Then there exists such that for all ,

satisfies (*) and (**). By assumption

is maximal for , so . Then a theorem by Farkas (or the dual theorem of linear programming) implies that there exists such that

where and . Now multiply the equation

by and sum up

After some simple arithmetic, we find that

Back to the main index for Future directions in algorithmic number theory.