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

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

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

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

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

Следствия

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

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

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

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

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

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

и

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

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

Литература

• Шаблон:Статья
• Шаблон:Книга