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

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

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

[math]\displaystyle{ (X-1)^n \equiv X^n - 1 \pmod{n, X^r - 1} \, }[/math],

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

Следствия

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

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

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

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

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

[math]\displaystyle{ (X-1)^n \equiv X^n - 1 \pmod{n, X^r - 1} }[/math]

и

[math]\displaystyle{ (X+2)^n \equiv X^n + 2 \pmod{n, X^r - 1} }[/math],

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

Литература

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