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

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

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

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

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

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

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

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

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

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

hence

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

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

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

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

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

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

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

and

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

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

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