WikiSort.ru - Не сортированное

Гипотеза Агравала, высказанная Маниндрой Агравалом в 2002^[1], образует основу для теста Агравала — Каяла — Саксены. Гипотеза Агравала утверждает:

Пусть ${\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}}}$ .

Следствия

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

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

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

Примечания

Литература

• Manindra Agrawal, Neeraj Kayal, Nitin Saxena. PRIMES is in P. — 2004. — Т. 160, вып. 2. — С. 781–793. — DOI:10.4007/annals.2004.160.781.
• Lenstra H. W., Carl Pomerance. Remarks on Agrawal’s conjecture.. — American Institute of Mathematics, 2013.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.