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

$$\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.

$$\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

$$\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$,

$$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

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

and therefore by assumption (*)

$$\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$,

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

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

$$\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

$$\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

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

by $a_k p_j$ and sum up

$$\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

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

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