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

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

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

• $\mathbb{Z}/n\mathbb{Z}$ is a subring of $A$ with $\char93 A \leq n^d$, and there exists $\sigma \in {\mathrm{Aut}}A$ with:
  • $\sigma^d \alpha = \alpha$;
  • for all $q \mid d$ prime, $\sigma^{d/q}(\alpha) - \alpha \in A^*$; and
  • $\sigma \alpha=\alpha^n$;
• Equivalently, $A \cong (\mathbb{Z}/n\mathbb{Z})[X]/(f)$ as a ring with $X \mapsto \alpha$ for some monic polynomial $f \in (\mathbb{Z}/n\mathbb{Z})[X]$ of degree $d$ satisfying:
  • $f(X) \mid f(X^n)$;
  • $f(X) \mid (X^{n^d}-X)$; and
  • for all primes $q \mid d$, $(f,X^{n^{d/q}}-X)=(1)$.

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

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

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

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

• $q_i>1$, $q_i$ pairwise coprime;
• $r_i$ prime, $q_i \mid (r_i-1)$;
• The order of $n^{(r_i-1)/q_i}$ modulo $r_i$ is $q_i$; and
• $d=\prod q_i$ satisfies
  $$(\log n/\log 2)^2 < d < c(\log n/\log 2)^2$$
  and $\max r_i<d$.

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.