Agrawal: A Polynomial Time Algorithm for Testing Primality

The primality testing algorithm we present is based upon the following identity: $n$ is prime if and only if

$$(1+X)^n \equiv 1 + X^n \pmod{n},$$

where we consider this congruence as an identity in the polynomial ring $(\mathbb{Z}/n\mathbb{Z})[X]$. This easily gives a randomized algorithm which runs in polynomial time: rather than verifying it completely (which would be far too expensive), you verify it modulo a randomly chosen degree $\log n$ polynomial $Q(X)$; repeating this sufficiently often, you expect to witness a failure of this congruence to hold fairly quickly if $n$ is composite.

Conjecture. To prove that $n$ is prime, it is enough to let $Q(X)$ run over the set

$$\{X-1,X^2-1,\dots,X^{\log^2 n}-1\}.$$

We were unable to prove this conjecture, but, instead the modified conjecture, which is then a proposition:

Proposition. [Modified conjecture] To prove that $n$ is prime, it is enough to let $Q(X)$ run over the set

$$R=\{(X+a)^r-1:1 \leq r \leq 16(\log n)^5, 1 \leq a \leq 8(\log n)^{7/2}\},$$

except when $n$ has a `small' prime factor ( $\leq (\log n)^5$).

Remark. One can replace the assumption that $n$ does not have a small prime factor by adding to the list the polynomials $X^k$.

For a fixed $r$, this gives only that $n$ is a prime power, which is a condition readily checked.

We now prove the modified conjecture.

If $n$ is prime, clearly all of these conditions will hold.

Assume that $n$ is composite and does not have a `small' prime factor. Assume that

$$(1+X)^n \equiv 1+X^n \pmod{n,Q(X)}$$

for every $Q(X) \in R$. First, observe that $n$ is not a prime power. This follows as

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

so substituting $X$ for $X+1$ everywhere we get

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

and substituting $X^k$ for $X$ we get

$$(X^k-1)^n \equiv X^{nk}-1 \pmod{n,X^r-1}$$

hence

$$\prod_{k<r}(X^k-1)^n \equiv \prod_{k<r}(X^{kn}-1)$$

so $r^n \equiv r \pmod{n}$ for all $r \leq 16(\log n)^5$.

Suppose $p^2 \mid n$ for $p$ a prime. Then $r^{n-1} \equiv 1 \pmod{p^2}$ ($n$ does not have a small prime divisor) so $r^{\gcd(n-1,p(p-1))} \equiv 1 \pmod{p^2}$ as the group is cyclic. Therefore $r^{p-1} \equiv 1 \pmod{p^2}$ for all $r \leq 16(\log n)^5$. A simple counting argument (look at all of the possible numbers whose prime divisors are all smaller than $(\log n)^2$, the identity holds for them but there are more than $p$ of them) shows that this cannot happen.

Assume that $n$ is composite but not a prime power. Let $p \mid n$, $p$ prime, and fix $r$. Now:

Claim. We have

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

for $1 \leq a \leq 8(\log n)^{7/2}$ if and only if

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

for $1 \leq a \leq 8(\log n)^{7/2}$.

This can be seen by replacing $X$ by $X-a$ as appropriate.

Definition. A number $m$ is introspective for $g(X)$ if

$$g(X)^m \equiv g(X^m) \pmod{p,x^r-1}.$$

Both $n$ and $p$ are introspective for $X-a$, $1 \leq a \leq 8(\log n)^{7/2}$. Indeed, a prime $p$ is trivially introspective for every polynomial.

Observe that if $m_1$ and $m_2$ are introspective for $g(X)$, then so is $m_1m_2$. This is clear as

$$g(X)^{m_1m_2} \equiv g(X^{m_1})^{m_2} \equiv g(X^{m_1m_2}) \pmod{p,X^r-1}.$$

Secondly, observe trivially that if $m$ is introspective for $g_1(X)$ and $g_2(X)$, then it is for $g_1(X)g_2(X)$.

Now let $I=\{n^ip^j:i,j \geq 0\}$ and

$$T=\left\{\textstyle{\prod}_{1 \leq a \leq 8(\log n)^{7/2}} (X-a)^{e_a}:e_a \geq 0\right\}.$$

Observe that every $m \in I$ is introspective for every $g(X) \in T$.

Let $t$ be the order of the group generated by $n$ and $p$ in $(\mathbb{Z}/r\mathbb{Z})^*$. There are $>t$ elements in $I$ less than or equal to $n^{2\sqrt{t}}$.

Furthermore, there are $>n^{2\sqrt{t}}$ distinct polynomials of degree $<t$ which are distinct modulo $p$ and $h(X)$, where $h(X)$ is an irreducible factor of the $r$th cyclotomic polynomial in $\mathbb{F}_p$. We show this as follows.

The number of polynomials in $T$ of degree $<t$ is at least $2^{\min\{t,8(\log n)^{7/2}\}}$ by simply considering products of distinct linear factors in $T$. Assume that $t > 4(\log n)^2$ and $t <16(\log n)^5$. (We will come back to this: we can choose the value of $r$ to obtain it.) Then

$$n^{2\sqrt{t}}=2^{2\sqrt{t}\log n}<2^t$$

and

$$n^{2\sqrt{t}}<n^{8(\log n)^{5/2}}=2^{8(\log n)^{7/2}}.$$

Let $F=\mathbb{F}_p[X]/(h(X))$, and let $g_1(X),g_2(X)$ be of degree $<t$ in $T$ and $g_1(X) \neq g_2(X)$. Suppose $g_1(X)=g_2(X) \pmod{p,h(X)}$. Then

$$g_1(X^m) \equiv g_1(X)^m \equiv g_2(X)^m \equiv g_2(X^m) \pmod{p,h(X)}$$

for all $m \in I$. Therefore $X^m$ is a root in $F$ of the polynomial $g_1(Y)-g_2(Y)$. This is a contradiction, as each of the elements $X^m$ are distinct (they are roots of unity in the field) for the $t$ representatives of the group generated by $n$ and $p$, but the degree of $g_1(Y)-g_2(Y)$ is $<t$.

Let $m_1 \equiv m_2 \pmod{r}$, $m_1 \neq m_2 \in I$ and $m_1,m_2 \leq n^{2\sqrt{t}}$; this is possible as $t$ is the order of the group generated by $n$ and $p$ in $\mathbb{Z}/r\mathbb{Z}$. Let $g(X) \in T$ be of degree $<t$. Then

$$g(X)^{m_1} \equiv g(X^{m_1}) \equiv g(X^{m_2}) \equiv g(X)^{m_2} \pmod{p,h(X)}$$

so $g(X) \pmod{h(X),p}$ is a root in $F$ of the polynomial $Y^{m_1}-Y^{m_2}$. Since $g$ was an arbitrary element of $T$, each $g(X)$ is a root of this polynomial with degree $\leq n^{2\sqrt{t}}$ but there are more than $n^{2\sqrt{t}}$ of them, contradiction.

Finally, we show that $t > 4(\log n)^2$ and $t <16(\log n)^5$. Suppose the order of $n$ is $\leq 4(\log n)^2$ in $(\mathbb{Z}/r\mathbb{Z})^*$. Then $r \mid \prod_{d \leq 4(\log n)^2}(n^d-1) < 2^{16(\log n)^5}$. Now use the fact that the least common multiple of the first $k$ numbers is at least $2^k$.

It is easy to see that this algorithm has runtime $(\log n)^{10.5}$.

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