# What is the current status of Agrawal's conjecture?

In their famous 'Primes is in P' paper Agrawal, Kayal and Saxena stated the following conjecture:

If for coprime integers $n$ and $r$ the equality $(X-1)^n = X^n - 1$ holds in $\mathbb{Z}_n[X]/(X^r-1)$ then either $n$ is prime or $n^2 = 1 \pmod{r}$.

If true this would give a beautiful characterization of primes that could be easily transformed into a fast ($O(\log^{3+\epsilon}{n})$) and deterministic primality test.

Shortly after publishing 'Primes is in P' Hendrik Lenstra noticed that the conjecture may not be valid for $r=5$ and $n$ of the very special form (see Lenstra's and Pomerance's note, p.30). It was unknown whether any such $n$ existed but Carl Pomerance gave a heuristic argument convincing that there should be infinitely many $n$'s sharing these, apparently rare, properties. I'm not aware of any strict proof for this.

It may also happen that the conjecture in a modified form (if we restrict $r$ to be greater than $\log{n}$) can be still true.

Martin Mačaj (see Some remarks and questions about the AKS algorithm and related conjecture) gave another version of this conjecture together with a proof that relied on yet another unsolved problem.

Does anyone know if there were any advances in this area in the recent years?

-

I had some students look at this problem during an REU. A group proved that the conjecture is true if $r > n/2$, that's not too hard and can certainly be improved. Another group tried to find a counterexample using the computer for $r=5$, without success. I agree with Lenstra and Pomerance that the conjecture should be false in general.

-

I found a paper here: http://eprint.iacr.org/2009/008.pdf which generalizes a result from Lenstra's and Pomerance's paper.

The paper is "A note on Agrawal conjecture" by Roman Popovych.

Here is the abstract:

We prove that Lenstra proposition suggesting existence of many counterexamples to Agrawal conjecture is true in a more general case. At the same time we obtain a strictly ascending chain of subgroups of the group (Zp[X]/(Cr(X)))* and state the modified conjecture that the set {X-1, X+2} generate big enough subgroup of this group.

Here is the url for a paper from a student scientific conference containing some numerical results:

-