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

Гипотеза Агравала, высказанная Маниндрой Агравалом в 2002, образует основу для теста Агравала — Каяла — Саксены. Гипотеза Агравала утверждает:

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

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

то либо $n$ является простым, либо $n^{2}\equiv 1{\pmod {r}}$.

Следствия

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

Верность или ложность гипотезы

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

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

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

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

и

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

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

Литература

• 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.