Гипотеза Агравала - Agrawal's conjecture

В теории чисел , гипотеза Агравала , из - за Маниндр Агравал в 2002 году, является основой для теста круговом АКСА . Формально гипотеза Агравала гласит:

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

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

то либо простое, либо${\ displaystyle n}$${\ Displaystyle п ^ {2} \ эквив 1 {\ pmod {r}}}$

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

Если бы гипотеза Агравала была верной, это уменьшило бы сложность выполнения теста простоты AKS с до . ${\ Displaystyle {\ тильда {O}} (\ log ^ {10.5} п)}$${\ Displaystyle {\ тильда {O}} (\ log ^ {3} п)}$

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

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

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

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

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

Примечания

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

• Проект Primaboinca