Гипотеза Агравала - Agrawals conjecture - Wikipedia

В теория чисел, Гипотеза Агравала, из-за Маниндра Агравал в 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}}(\log ^{10.5}n)}$ к ${\displaystyle {\tilde {O}}(\log ^{3}n)}$.

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

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

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

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

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

И гипотеза Агравала, и гипотеза Поповича проверяются распределенных вычислений проект Primaboinca, который был запущен в 2010 году на основе BOINC. По состоянию на июнь 2017 года в проекте не обнаружено контрпримера для ${\displaystyle n<10^{12}}$.

Примечания

1. Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (2004). "ПРИМЕР в П" (PDF). Анналы математики. 160 (2): 781–793. Дои:10.4007 / анналы.2004.160.781. JSTOR  3597229.
2. Раджат Бхаттачарджи, Прашант Панди (апрель 2001 г.). «Проверка первичности». Технический отчет. ИИТ Канпур.
3. Нирадж Каял, Нитин Саксена (2002). «К детерминированному полиномиальному тесту на простоту». Технический отчет. ИИТ Канпур. CiteSeerX  10.1.1.16.9281.
4. Саксена, Нитин (декабрь 2014 г.). «Генерация первичности и простых чисел» (PDF). UPMC в Париже. Архивировано из оригинал (PDF) 25 апреля 2018 г.. Получено 24 апреля 2018.
5. Lenstra, H.W .; Померанс, Карл (2003). «Замечания к гипотезе Агравала» (PDF). Американский институт математики. Получено 16 октября 2013.
6. Попович, Роман (30 декабря 2008 г.), Заметка о гипотезе Агравала (PDF), получено 21 апреля 2018

внешняя ссылка

• Проект Primaboinca