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

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

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

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

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

Следствия

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

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

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

Примечания

↑ Agrawal, Kayal, Saxena, 2004, с. 781–793.
↑ Lenstra, Pomerance, 2013.
↑ Popovych, Roman, A note on Agrawal conjecture (PDF), Архивировано (PDF) 15 октября 2018, Дата обращения: 27 марта 2018 Источник (неопр.). Дата обращения: 27 марта 2018. Архивировано 15 октября 2018 года.

Литература

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

Похожие исследовательские статьи

Тест Миллера — Рабина — вероятностный полиномиальный тест простоты. Тест Миллера — Рабина, наряду с тестом Ферма и тестом Соловея — Штрассена, позволяет эффективно определить, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее тест Миллера — Рабина часто используется в криптографии для получения больших случайных простых чисел.

<span class="mw-page-title-main">Факторизация целых чисел</span> Разложение натурального числа на простые множители

Факториза́цией натурального числа называется его разложение в произведение простых множителей. Существование и единственность такого разложения следует из основной теоремы арифметики.

Целое число $\text{[math]}$ называется квадратичным вычетом по модулю $\text{[math]}$ , если разрешимо сравнение:

\text{[math]}

<span class="mw-page-title-main">Функция Эйлера</span> мультипликативная арифметическая функция

Фу́нкция Э́йлера $\text{[math]}$ — мультипликативная арифметическая функция, значение которой равно количеству натуральных чисел, меньших либо равных $\text{[math]}$ и взаимно простых с ним.

Алгоритм Полига — Хеллмана — детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Одной из особенностей алгоритма является то, что для простых чисел специального вида можно находить дискретный логарифм за полиномиальное время.

Алгоритм Адлемана — первый субэкспоненциальный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Алгоритм был предложен Леонардом Максом Адлеманом в 1979 году. Леонард Макс Адлеман — американский учёный-теоретик в области компьютерных наук, профессор компьютерных наук и молекулярной биологии в Университете Южной Калифорнии. Он известен как соавтор системы шифрования RSA и ДНК-вычислений. RSA широко используется в приложениях компьютерной безопасности, включая протокол HTTPS.

Тест Аграва́ла — Кая́ла — Саксе́ны — единственный известный на данный момент универсальный полиномиальный, детерминированный и безусловный тест простоты чисел, основанный на обобщении малой теоремы Ферма на многочлены.

Число Кармайкла — составное число $\text{[math]}$ , которое удовлетворяет сравнению $\text{[math]}$ для всех целых $\text{[math]}$ , взаимно простых с $\text{[math]}$ , другими словами — псевдопростое число по каждому основанию $\text{[math]}$ , взаимно простому с $\text{[math]}$ . Такие числа относительно редки, но их бесконечное число, наименьшее из них — 561; существование таких чисел делает недостаточным условие простоты малой теоремы Ферма, и не позволяет применять тест Ферма как универсальное средство проверки простоты.

Тест Соловея — Штрассена — вероятностный тест простоты, открытый в 1970-х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном. Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью он может дать неверный ответ. Основное преимущество теста заключается в том, что он, в отличие от теста Ферма, распознает числа Кармайкла как составные.

Метод квадратичного решета — метод факторизации больших чисел, разработанный Померанцем в 1981 году. Долгое время превосходил другие методы факторизации целых чисел общего вида, не имеющих простых делителей, порядок которых значительно меньше $\text{[math]}$ . Метод квадратичного решета представляет собой разновидность метода факторных баз . Этот метод считается вторым по быстроте. И до сих пор является самым быстрым для целых чисел до 100 десятичных цифр и устроен значительно проще чем общий метод решета числового поля. Это универсальный алгоритм факторизации, так как время его выполнения исключительно зависит от размера факторизуемого числа, а не от его особой структуры и свойств.

Алгоритм Диксона — алгоритм факторизации, использующий в своей основе идею Лежандра, заключающуюся в поиске пары целых чисел $\text{[math]}$ и $\text{[math]}$ таких, что $\text{[math]}$ и $\text{[math]}$

Общий метод решета числового поля — метод факторизации целых чисел. Является наиболее эффективным алгоритмом факторизации чисел длиной более 110 десятичных знаков. Сложность алгоритма оценивается эвристической формулой

\text{[math]}

Специальный метод решета числового поля является методом факторизации целых чисел особого вида. Из него был получен общий метод решета числового поля, являющийся наиболее эффективным алогритмом факторизации больших целых чисел $\text{[math]}$ . Метод эффективен для целых чисел вида r^e ± s, где r $\text{[math]}$ N s $\text{[math]}$ Z, r и s невелики(например Числа Мерсенна).

Гипотеза Буняковского гласит, что если $\text{[math]}$ — целозначный неприводимый многочлен и d — наибольший общий делитель всех его значений в целых точках, то целозначный многочлен $\text{[math]}$ принимает бесконечно много простых значений.

В теории чисел факторизация методом непрерывных дробей (CFRAC) — это алгоритм разложения целых чисел на простые множители. Это алгоритм общего вида, пригодный для факторизации произвольного целого $\text{[math]}$ .

В теории чисел простым числом Вифериха называется простое число $\text{[math]}$ , такое, что $\text{[math]}$ делит $\text{[math]}$ , что является усилением утверждения малой теоремы Ферма, утверждающей, что любое нечетное простое $\text{[math]}$ делит $\text{[math]}$ . Эти простые числа впервые описаны Артуром Виферихом в 1909-м году в работе, относящейся к великой теореме Ферма. К тому времени обе теоремы Ферма были хорошо известны математикам.

Гипотеза Аго — Джуги — теоретико-числовая гипотеза о числах Бернулли $\text{[math]}$ , согласно которой $\text{[math]}$ является простым числом тогда и только тогда, когда $\text{[math]}$ .

Алгори́тм Тоне́лли — Ше́нкса относится к модулярной арифметике и используется для решения сравнения

\text{[math]}

Алгоритм Шуфа — эффективный алгоритм подсчёта числа точек на эллиптической кривой над конечным полем. Алгоритм имеет приложения в эллиптической криптографии, где важно знать число точек, чтобы судить о трудности решения задачи дискретного логарифмирования на группе точек на эллиптической кривой.

В математике и информатике сертификат простоты — это строгое доказательство того, что число является простым. Наличие сертификата простоты позволяет проверить, что число простое, не прибегая к тестам простоты.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.