Гипотеза Агравала

Если гипотеза Агравала верна, это уменьшит вычислительную сложность теста Агравала — Каяла — Саксены с ${\displaystyle {\tilde {O}}(\log ^{6}n)}$ до ${\displaystyle {\tilde {O}}(\log ^{3}n)}$.

Гипотеза Агравала была проверена с помощью компьютера для ${\displaystyle r<100}$ и ${\displaystyle n<10^{10}}$. Однако эвристический аргумент Карла Померанса и Хендрика Ленстры предполагает, что имеется бесконечно много контрпримеров[2]. В частности, эвристические аргументы показывают, что такие контрпримеры имеют асимптотическую плотность, большую ${\displaystyle {\tfrac {1}{n^{\varepsilon }}}}$ для любого ${\displaystyle \varepsilon >0}$.

Если гипотеза Агравала не верна согласно вышеприведённым аргументам, модифицированная версия гипотезы Поповича может остаться верной:

Пусть ${\displaystyle n}$ и ${\displaystyle r}$ — два взаимно простых положительных целых. Если

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

и

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

тогда либо ${\displaystyle n}$ простое, либо ${\displaystyle n^{2}\equiv 1{\pmod {r}}}$[3].

• Manindra Agrawal, Neeraj Kayal, Nitin Saxena. PRIMES is in P. — 2004. — Т. 160, вып. 2. — С. 781–793. — doi:10.4007/annals.2004.160.781. — .
• Lenstra H. W., Carl Pomerance. Remarks on Agrawal’s conjecture.. — American Institute of Mathematics, 2013.