Pomerance and Bleichenbacher: Constructing Finite Fields

Consider the following problem: Given a prime $ p$ and an integer $ d>1$, find an irreducible polynomial $ f \in \mathbb{F}_p[X]$ of degree $ d$. And do so in time polynomial in $ d$ and $ \log p$. There is a randomized algorithm which attacks this problem by picking a polynomial at random (approximately $ 1$ out of every $ d$ 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 $ d=2$, this is a difficult problem, equivalent to finding a quadratic nonresidue modulo $ p$.

Assuming the ERH, Adleman and Lenstra have a solution to this problem. Unconditionally, they also find an irreducible polynomial of degree $ d'$ with $ d \leq d' < cd\log p$, where $ c$ is an effectively computable number. Letting $ d=(\log n)^2$ and $ n=p$ (where you do not know a priori if $ n$ is prime), the polynomial produced has degree $ O(\log^3 n)$, and the runtime of the AKS algorithm becomes $ \widetilde{O}((\deg f)^{3/2} \log^3 n)=\widetilde{O}((\log n)^{15/2})$. We improve this theorem to the following:

Theorem. Such a polynomial can be produced with $ d \leq d' \leq 4d$ for $ p$ sufficiently large and $ d \geq (\log p)^{11/6+\epsilon}$.

The bound for the `sufficiently large' part depends effectively on the choice of $ \epsilon$.

Theorem. There is an effectively computable function $ N_\epsilon$ and a deterministic algorithm such that if $ \epsilon>0$, $ n>N_\epsilon$, and $ D>(\log n)^{11/6+\epsilon}$, the algorithm produces pairs $ (q_1,r_1),\dots,(q_k,r_k)$ such that for each $ i$, $ r_i$ is prime, $ r_i<D$, $ q_i \mid r_i-1$, the order of $ n^{(r_i-1)/q_i}$ modulo $ r_i$ is $ q_i$. Further, the $ q_1,\dots,q_k$ are pairwise coprime, and $ D \leq \prod_i q_i \leq 4D$. This algorithm runs in time $ \widetilde{O}_{\textup{eff}}(D^{12/11})$.

Let $ \eta_i$ be the Gaussian period of degree $ q_i$ in $ \mathbb{Q}(\zeta_{r_i})$ (the trace of $ \zeta_{r_i}$ into the unique subfield of degree $ q_i$ over $ \mathbb{Q}$). The element $ \eta=\eta_1 \dots \eta_k$ has degree $ q_1 \dots q_k$ over the rationals (by coprimality). If $ n$ is prime, and if $ f(x)$ is the minimal polynomial of $ \eta$ then $ f \bmod n$ is irreducible over $ \mathbb{F}_n$. Checking if $ f(X) \mid f(X^n)$ in $ (\mathbb{Z}/n\mathbb{Z})[X]$ (together with some other conditions), we see that $ f$ gives rise to a pseudofield.

Let $ x=D^{6/11-\epsilon/4}$. Throughout, we assume that $ n$ is `sufficiently large' with the bound being effectively computable, depending only on the choice of $ \epsilon$.

Proposition. All but $ O(x/\log^3 x)$ primes $ r \leq x$ have a prime $ q \mid (r-1)$ with $ q > x^{1/(\log\log x)^2}$ and the order of $ n^{(r-1)/q}$ modulo $ r$ is equal to $ q$.

Therefore up to $ x$, 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 $ r$ such that $ r-1$ is smooth due to Pomerance and Shperlinski.

Proposition. Let $ Q$ be a set of primes $ q$ with $ x^{1/(\log \log x)^2} < q \leq x^{1/2}$ and $ \sum_{q \in Q}1/(q-1) < (3-\epsilon)/11$. Then there are $ >\delta x/\log^2 x$ primes $ r \leq x$ such that $ r-1$ is free of primes from $ Q \cup (x^{1/2},x)$.

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 $ Q$ be the set of primes $ q$ in the first proposition satisfying $ q \leq \sqrt{x}$. Then

$\displaystyle \sum_{q \in Q} \frac{1}{q-1} \geq \frac{3-\epsilon}{11}. $

Proof. If this inequality did not hold, then by the first and second propositions, there must be primes $ r \leq x$ having the properties of both propositions. By the first proposition, $ r-1$ has a prime factor $ q>x^{1/)\log \log x)^2}$ and the order of $ n^{(r-1)/q}$ modulo $ r$ is equal to $ q$. By one of the properties in the second proposition, $ q \leq x^{1/2}$. Then $ q \in Q$. This contradicts the second proposition. $ \qedsymbol$

Proposition. There exists a subset of $ Q$ in the corollary with product in the interval $ [D,4D]$.

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

Theorem. [Continuous Frobenius theorem] If $ S$ is an open subset of $ \mathbb{R}_{>0}$, $ S$ is closed under addition, and $ 1 \not\in S$, then for any $ t$, $ 0 < t \leq 1$, the $ du/u$ measure of $ S \cap (0,t)$ is $ \leq t$, i.e.

$\displaystyle \int_0^t \chi_S(u) \frac{du}{u} \leq t $

where $ \chi_S(u)$ is the characteristic function of $ S$.

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

$\displaystyle \pi(x,k,a)=\char93 \{p \leq x: x \equiv a \pmod{k}\} \sim \pi(x)/\phi(k) $

as $ x \to \infty$. The Siegel-Walfisz theorem states that this is true for $ k < (\log x)^A$ for any fixed $ A$. 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 $ S_t=S \cap (0,t)=\bigcup_{i=1}^{n} (a_i,b_i)$ (i.e. $ S_t$ contains only finitely many intervals). Second, since $ 1 \not\in S$, for all $ (h_1,\dots,h_n) \in \mathbb{N}_{\geq 0}^n$ either $ \sum_{i=1}^{n} h_ia_i \geq 1$ or $ \sum_{i=1}^{n} h_i b_i \leq 1$ (*). Now fix $ b_1,\dots,b_n$ such that $ b_1 > b_2 > \dots > b_n$ and consider all sets $ \bigcup_{i=1}^{n} (a_i,b_i)$ satisfying $ b_1 \geq a_1 \geq b_2 \geq \dots \geq b_n \geq a_n$ (**) as well as condition (*). Under these conditions, there exists a maximum to $ \sum_{i=1}^n (\log(b_i) - \log(a_i))$. We may thus assume that $ S_t=\bigcup_{i=1}^{n} (a_i,b_i)$ is a maximum. We show in the paper that we can assume that $ b_1 > a_1 > b_2 > \dots > b_n > a_n$.

Let $ U=\{h \in \mathbb{N}_{\geq 0}^n:ha=1\}$ with $ a=(a_1,\dots,a_n)$. Let $ a_{n+1}=b_{n+1}=0$. For all $ h=(h_1,\dots,h_n) \in U$ and $ 1 \leq k \leq n$,

$\displaystyle h_k\left(\sum_{i=1}^{n} (b_i-a_i)h_i\right) \leq h_k(b_k-b_{k+1}). $

This is trivial if $ h_k=0$, and otherwise, $ \sum_{i=1}^{n} a_i h_i =1$ which implies

$\displaystyle \sum_{i=1}^{n} a_i h_i -a_k + a_{k+1} < 1. $

and therefore by assumption (*)

$\displaystyle \sum_{i=1}^{n} b_i h_i - b_k + b_{k+1} \leq 1. $

Let $ v=(v_1,\dots,v_n) \in \mathbb{R}^n$ such that $ vh \geq 0$ for all $ h \in U$. Then there exists $ \epsilon>0$ such that for all $ 0 \leq x \leq \epsilon$,

$\displaystyle \bigcup_{i=1}^n (a_i+v_i x, b_i) $

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

$\displaystyle \sum_{i=1}^{n} (\log b_i - \log(a_i+v_ix)) $

is maximal for $ x=0$, so $ \sum_{i=1}^{n} v_i/a_i \geq 0$. Then a theorem by Farkas (or the dual theorem of linear programming) implies that there exists $ p_j \geq 0$ such that

$\displaystyle \sum_{i=1}^{\ell} h_{ij} p_j = \frac{1}{a_i} $

where $ U=\{h_1,\dots,h_\ell\}$ and $ h_j=(h_{1j},\dots,h_{nj})$. Now multiply the equation


by $ a_k p_j$ and sum up

$\displaystyle \sum_{k=1}^n \sum_{j=1}^{\ell} a_k p_j h_{kj} \left(\sum_{i=1}^n ...
..._{ij}\right) \leq
\sum_{k=1}^{n} \sum_{j=1}^\ell a_k p_j h_{kj} (b_k-b_{k+1}). $

After some simple arithmetic, we find that

$\displaystyle \sum_{i=1}^n (\log b_i - \log a_i) \leq t. $
