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

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

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

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

Если гипотеза Агравала верна, это уменьшит вычислительную сложность теста Агравала — Каяла — Саксены с ${\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. — JSTOR 3597229.
• Lenstra H. W., Carl Pomerance. Remarks on Agrawal’s conjecture.. — American Institute of Mathematics, 2013.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.