Lenstra: Primality Testing with Pseudofields

This is joint work with Carl Pomerance.

If $ f,g$ are real-valued functions on a set $ X$ and $ g>0$, then we say $ f=\widetilde{O}(g)$ if there exists $ c \in \mathbb{R}_{>0}$ such that for all $ x \in X$, $ \vert f(x)\vert \leq g(x) \max\{2,\log g(x)\}^c$.

Theorem. There is a deterministic algorithm that given $ n \in \mathbb{Z}$, $ n>1$, correctly decides whether or not $ n$ is prime and that has runtime $ \widetilde{O}((\log n)^6)$.

The theorem of AKS begins (in brief) as follows. Let $ n \in \mathbb{Z}_{>1}$ be a positive integer, $ r$ a prime number with $ r \nmid n$, and

$\displaystyle (X+a)^n \equiv X^n+a \pmod{n,X^r-1} $

for a small set of $ a$, and the multiplicative order of $ n$ modulo $ r$ is at least $ c(\log n)^2$. Together with other conditions, we conclude $ n$ is a prime. This has runtime $ \widetilde{O}(r^{3/2}(\log n)^3)$. For $ r=O((\log n)^5)$, we get $ \widetilde{O}((\log n)^{21/2})$ with effective constant. For an ineffective constant, one can get $ \widetilde{O}((\log n)^{15/2})$. It would be optimal to have $ \widetilde{O}((\log n)^6)$, which would require $ r=\widetilde{O}((\log n)^2)$ but here we run into Artin's conjecture on primes with prescribed primitive root. To get around this, we generalize the situation slightly to give more parameters.

In fact, we replace $ X^r-1$ by $ (X^r-1)/(X-1)=X^{r-1}+\dots+X+1$; the proof remains essentially unchanged. Instead of considering congruences, we instead think of equalities in the ring

$\displaystyle A=\mathbb{Z}[X]/(n,X^{r-1}+\dots+X+1) \supset \mathbb{Z}/n\mathbb{Z}. $

This is a Galois extension of $ \mathbb{Z}/n\mathbb{Z}$ of degree $ r-1$. We now replace the polynomial $ X^{r-1}+\dots+X+1$ with other polynomials $ f(X)$ for which the same proof techniques apply. In this case, $ A$ is a field if and only if $ n$ is a prime number and $ n$ is a primitive root modulo $ r$. We are led to introduce rings that `try very hard' to be fields.

Definition. A pseudofield is a pair $ A,\alpha$ where $ A$ is a ring (commutative with $ 1$) and $ \alpha \in A$ such that there exists $ n \in \mathbb{Z}_{>1}$ and $ d \in \mathbb{Z}_{>0}$ satisfying:

Also equivalently, a pseudofield is characterized by the conditions that $ A \supset \mathbb{Z}/n\mathbb{Z}$ be Galois with cyclic group generated by $ \sigma$, $ \alpha$ generates $ A$ as a ring, and $ \sigma \alpha=\alpha^n$.

Theorem. There is a deterministic algorithm that given $ n \in \mathbb{Z}_{>1}$ and $ f \in (\mathbb{Z}/n\mathbb{Z})[X]$ decides if $ (\mathbb{Z}/n\mathbb{Z})[X]/(f)$ is a pseudofield in time

$\displaystyle \widetilde{O}((d+\log n)d\log n). $

It is routine to verify this using the second set of conditions.

Example.

  1. If $ r$ is a prime with $ r \nmid n$, then $ A=(\mathbb{Z}/n\mathbb{Z})[X]/(X^{r-1}+\dots+1)$ is a pseudofield if and only if the order of $ n$ modulo $ r$ is $ r-1$.
  2. If $ n$ is prime, then $ A,\alpha$ is a pseudofield if and only if $ A$ is a field and $ A=\mathbb{F}_n[\alpha]$.
  3. If $ A=\mathbb{Z}/n\mathbb{Z}$ (so that $ d=1$) and $ \alpha = (a \bmod n)$, then $ A,\alpha$ is a pseudofield if and only if $ a^n \equiv a \pmod{n}$--in other words, $ n$ is a pseudoprime to base $ a$.

Theorem. Let $ A,\alpha$ be a pseudofield of characteristic $ n$ and degree $ d$ such that $ d>(\log n/\log 2)^2$, $ n$ has no prime factor $ \leq k=\lfloor \sqrt{d}(\log n/\log 2)\rfloor$, and such that

$\displaystyle (\alpha+a)^n = a^n+a $

for $ a=1,2,\dots,k \pmod{n}$. Then $ n$ is a power of a prime number.

The proof uses: for each prime $ p \mid n$, there exists a unique $ \tau \in \langle \sigma \rangle$ such that for all $ \beta \in A$, $ \tau(\beta) \equiv \beta^p \pmod{pA}$. This is a result coming from Galois theory for rings.

This leads to a deterministic primality test with runtime equal to the time to construct the pseudofield plus the time to check the conditions; the latter takes time $ \widetilde{O}(d^{3/2}(\log n)^3)$.

In the context of primality testing, there is a procedure which converts any (honest) method for constructing finite fields to a method for checking primality. If the algorithm on input $ n$ crashes, then $ n$ was not prime; if it returns a polynomial $ f$, then one checks (efficiently) if this gives rise to a pseudofield, which then verifies that $ n$ is prime, and otherwise produces a proof that $ n$ is not prime.

Therefore we look for algorithms for constructing finite fields. Our construction relies on the following theorem:

Theorem. [Kummer 1846] For $ r$ prime and $ q \mid (r-1)$, put

$\displaystyle f_{q,r}=\prod_{\substack{i \in \mathbb{F}_r  i^q=1}}\biggl(X- \sum_{j^{(r-1)/q}=i} \zeta_r^j\biggr) \in \mathbb{Z}[X] $

where $ \zeta_r$ is a primitive $ r$th root of unity in $ \mathbb{C}$. The polynomial $ f$ is monic and irreducible of degree $ q$. If $ p$ is prime, $ p \neq r$, then $ (f_{q,r} \bmod p) \in \mathbb{F}_p[X]$ is irreducible if and only if the order of $ p^{(r-1)/q}$ modulo $ r$ is equal to $ q$.

Fact. Let $ A_i,\alpha_i$ be a pseudofield of characteristic $ n$ and degree $ d_i>1$ for $ i=1,2$ such that $ \gcd(d_1,d_2)=1$; then $ A_1 \otimes_{\mathbb{Z}} A_2,\alpha_1 \otimes \alpha_2$ is a pseudofield of characteristic $ n$ and degree $ d_1d_2$.

Theorem. There exists an effective computable constant $ c$ such that there is a deterministic algorithm that given $ n \in \mathbb{Z}_{>1}$ finds a finite sequence of pairs $ (r_1,q_1),\dots,(r_k,q_k)$ such that:

This algorithm runs in time $ \widetilde{O}((\log n)^{24/11})$, with an effective constant.




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