# AKS Algorithm Pseudoprimes

The AKS algorithm is based on the following fully deterministic primality check:

Let input $n>1$ and $a \in \mathbb{N}$ such that $(a,n)=1$. Then $n$ is prime if and only if $$\tag{1}(x+a)^n \equiv x^n + a \ (\text{mod}\ n).$$ This check involves computing $n$ binomial coefficients, which is too slow. AKS sped up their algorithm by reducing equation (1) modulo $x^r-1$ for an appropriate small $r$. However, in their paper, the authors claim "The problem now is that some composites $n$ may also satisfy the equation for a few values of $a$ and $r$ (and indeed they do)."

I am curious about the likelihood of encountering such a composite $n$, an "AKS-pseudoprime" if you will. The time-consuming part of the AKS algorithm is evaluating $$\tag{2}(x+a)^n \equiv x^n + a \ (\text{mod}\ x^r-1,n)$$ for values of $a$ between $1$ and $\lfloor\sqrt{\phi(r)}\log{n}\rfloor$. I have checked equation (2) on the first 10 million values of $n$, with $a=1$, and the equality fails immediately for all composite $n$ (i.e. it is unnecessary to increment $a$). Does anyone have an example of a composite number $n$ that satisfies equation (2) for any value of $a$?

-
Discussed here: mathoverflow.net/questions/45855/… –  Felipe Voloch Feb 5 '13 at 18:34
Thanks Felipe! This question is slightly different from Agrawal's conjecture, and in the original paper, Agrawal seems convinced that there are composite values of $n$ that 'appear' prime for some values of $a$, necessitating the for loop. Do you think I am likely to find any? –  Dominick Reinhold Feb 5 '13 at 19:09
For fixed $r$ and $a=1$ there should be "pseudoprimes". But they may be too big to be found. –  Felipe Voloch Feb 6 '13 at 1:25
What $r$ do you use? For $r=1$, the condition collapses to $2^n \equiv 2 \mod n$ which certainly has non-prime solutions. –  David Speyer Feb 7 '13 at 15:01
The value of $r$ used is very specific; namely $r$ is the smallest integer such that $o_r(n) > \log_2^2(n)$. The proof that such an $r$ exists (and is bounded above by ~$\log_2^5(n)$) is in the AKS paper, but an expanded (imho more understandable) proof can be found here: math.stackexchange.com/questions/119573/… –  Dominick Reinhold Feb 7 '13 at 19:00