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

В чисел теории гипотеза Агравала , выдвинутая Маниндрой Агравалом в 2002 году, составляет основу кругового теста AKS . Гипотеза Агравала формально утверждает:

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

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

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

Разветвления

Если бы гипотеза Агравала была верна, это снизило бы сложность теста простоты AKS во время выполнения с ${\tilde {O}}{\mathord {\left(\log ^{6}n\right)}}$ к ${\tilde {O}}{\mathord {\left(\log ^{3}n\right)}}$.

Правда или ложь

Гипотеза была сформулирована Раджатом Бхаттачарджи и Прашантом Панди в их диссертации 2001 года. Это было проверено вычислительно на $r<100$ и $n<10^{10}$, и для $r=5,n<10^{11}$.

Однако эвристический аргумент Карла Померанса и Хендрика В. Ленстры предполагает, что существует бесконечно много контрпримеров. В частности, эвристика показывает, что такие контрпримеры имеют асимптотическую плотность больше, чем ${\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}}$.

Распределенные вычисления

И гипотеза Агравала, и гипотеза Поповича были проверены проектом распределенных вычислений Primaboinca, который работал с 2010 по 2020 год на основе BOINC . Проект не нашел контрпримера, поиск в $10^{10}<n<10^{17}$.

Внешние ссылки

• Проект Примабоинка