5
$\begingroup$

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

$\endgroup$
8
  • 1
    $\begingroup$ Discussed here: mathoverflow.net/questions/45855/… $\endgroup$ Feb 5, 2013 at 18:34
  • $\begingroup$ 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? $\endgroup$ Feb 5, 2013 at 19:09
  • $\begingroup$ For fixed $r$ and $a=1$ there should be "pseudoprimes". But they may be too big to be found. $\endgroup$ Feb 6, 2013 at 1:25
  • $\begingroup$ What $r$ do you use? For $r=1$, the condition collapses to $2^n \equiv 2 \mod n$ which certainly has non-prime solutions. $\endgroup$ Feb 7, 2013 at 15:01
  • $\begingroup$ 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/… $\endgroup$ Feb 7, 2013 at 19:00

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.