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

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

Пусть и — два взаимно простых положительных целых числа . Если ${\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}}}$

Последствия

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

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

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

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

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

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

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

Примечания

1. Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (2004). «ПРАЙМС находится в P» (PDF) . Анналы математики . 160 (2): 781–793. дои : 10.4007/анналы.2004.160.781 . JSTOR  3597229.
2. Раджат Бхаттачарджи, Прашант Пандей (апрель 2001 г.). «Тестирование примитивности». Технический отчет . ИИТ Канпур .
3. Нирадж Каял, Нитин Саксена (2002). "К детерминированному тесту на простоту в полиномиальном времени". Технический отчет . IIT Kanpur. CiteSeerX 10.1.1.16.9281 . 
4. Saxena, Nitin (декабрь 2014 г.). "Primality & Prime Number Generation" (PDF) . UPMC Paris. Архивировано из оригинала (PDF) 25 апреля 2018 г. . Получено 24 апреля 2018 г. .
5. Lenstra, HW; Pomerance, Carl (2003). "Замечания о гипотезе Агравала" (PDF) . Американский институт математики . Получено 16 октября 2013 г. .
6. Попович, Роман (30 декабря 2008 г.), Заметка о гипотезе Агравала (PDF) , получено 21 апреля 2018 г.

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

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