Тест на примитивность

Тест на простоту — это алгоритм определения того, является ли входное число простым . Среди других областей математики он используется для криптографии . В отличие от факторизации целых чисел , тесты на простоту обычно не дают простых множителей , а лишь указывают, является ли входное число простым или нет. Факторизация считается сложной в вычислительном отношении проблемой, тогда как проверка на простоту сравнительно проста ( время ее выполнения зависит полиномиально от размера входных данных). Некоторые тесты на простоту доказывают, что число простое, в то время как другие, такие как Миллер-Рабин, доказывают, что число является составным . Следовательно, последние правильнее было бы называть тестами на составность , а не тестами на простоту.

Простые методы

Самый простой тест на простоту — это пробное деление : по заданному входному числу $n$ ли оно , проверьте, делится на любое простое число от 2 до ${\sqrt {n}}$(т.е. не оставляет ли деление остатка ). Если так, то $n$является составным . В противном случае это просто. Для любого делителя $p\geq {\sqrt {n}}$, должен быть еще один делитель $n/p\leq {\sqrt {n}}$и простой делитель $q$ из $n/p$, и поэтому ищем не более простых делителей ${\sqrt {n}}$ достаточно.

Например, рассмотрим число 100, делителями которого являются следующие числа:

1, 2, 4, 5, 10, 20, 25, 50, 100.

Когда все возможные делители до $n$проверяются, некоторые делители будут обнаружены дважды . Чтобы это заметить, рассмотрим список пар делителей 100:

$1\times 100,\;2\times 50,\;4\times 25,\;5\times 20,\;10\times 10,\;20\times 5,\;25\times 4,\;50\times 2,\;100\times 1$.

Продукты прошлого $10\times 10$являются противоположностью продуктов, появившихся ранее. Например, $5\times 20$ и $20\times 5$являются противоположностью друг друга. Далее, соотношение двух делителей $5\leq {\sqrt {100}}=10$ и $20\geq {\sqrt {100}}=10$. Это наблюдение распространяется на все $n$: все пары делителей $n$ содержат делитель, меньший или равный ${\sqrt {n}}$, поэтому алгоритму нужно искать только делители, меньшие или равные ${\sqrt {n}}$ чтобы гарантировать обнаружение всех пар делителей.

Кроме того, 2 — простое число, делящее 100, что сразу доказывает, что 100 не является простым числом. каждое положительное целое число, кроме 1, делится хотя бы на одно простое число Согласно основной теореме арифметики . Следовательно, алгоритму нужно искать только простые делители, меньшие или равные ${\sqrt {n}}$.

В качестве другого примера рассмотрим, как этот алгоритм определяет простоту числа 17. $4<{\sqrt {17}}<5$, и единственные простые числа $\leq {\sqrt {17}}$являются 2 и 3. Ни одно из них не делит 17, что доказывает, что 17 — простое число. В качестве последнего примера рассмотрим число 221. Имеем $14<{\sqrt {221}}<15$, и простые числа $\leq {\sqrt {221}}$ равны 2, 3, 5, 7, 11 и 13. Проверив каждое, обнаруживается, что $221/13=17$, доказывая, что 221 не является простым числом.

В тех случаях, когда невозможно вычислить список простых чисел $\leq {\sqrt {n}}$, также можно просто (и медленно) проверить все числа между $2$ и ${\sqrt {n}}$для делителей. Довольно простая оптимизация состоит в проверке делимости на 2 и только на нечетные числа между 3 и 3. ${\sqrt {n}}$, поскольку из делимости на четное число следует деление на 2.

Этот метод можно усовершенствовать и дальше. Обратите внимание, что все простые числа больше 3 имеют вид $6k+i$ для неотрицательного целого числа $k$ и $i\in \{1,5\}$. Действительно, каждое целое число имеет вид $6k+i$ для положительного целого числа $k$ и $i\in \{0,1,2,3,4,5\}$. Поскольку 2 деления $6k,6k+2$, и $6k+4$, и 3 деления $6k$ и $6k+3$, единственные возможные остатки по модулю 6 для простого числа больше 3 — это 1 и 5. Таким образом, более эффективный тест на простоту для $n$ состоит в том, чтобы проверить, является ли $n$ делится на 2 или 3, а затем проверить все числа вида $6k+1$ и $6k+5$ которые $\leq {\sqrt {n}}$. Это почти в три раза быстрее, чем проверка всех чисел до ${\sqrt {n}}$.

Обобщая далее, все простые числа, большие $c\#$ ( c primorial ) имеют вид $c\#\cdot k+i$ для $i,k$ положительные целые числа, $0\leq i<c\#$, и $i$ взаимно простой с $c\#$. Например, рассмотрим $6\#=2\cdot 3\cdot 5=30$. Все целые числа имеют вид $30k+i$ для $i,k$ целые числа с $0\leq i<30$. Теперь 2 деления $0,2,4,\dots ,28$, 3 деления $0,3,6,\dots ,27$, и 5 делит $0,5,10,\dots ,25$. Таким образом, все простые числа больше 30 имеют вид $30k+i$ для $i\in \{1,7,11,13,17,19,23,29\}$. Конечно, не все числа вида $c\#\cdot k+i$ с $i$ взаимно простой с $c\#$являются простыми. Например, $19\cdot 23=437=210\cdot 2+17=2\cdot 7\#+17$ не является простым, хотя 17 взаимно просто $7\#=2\cdot 3\cdot 5\cdot 7$.

Как $c$ растет, доля взаимно простых остатков к остаткам уменьшается, и поэтому время проверки $n$ уменьшается (хотя проверять делимость на все простые числа, меньшие $c$). Наблюдения, аналогичные предыдущим, можно применить рекурсивно , получив Решето Эратосфена .

Один из способов ускорить эти методы (и все остальные, упомянутые ниже) — предварительно вычислить и сохранить список всех простых чисел до определенной границы, например, всех простых чисел до 200. (Такой список можно вычислить с помощью Решето Эратосфена или алгоритм, проверяющий каждое приращение $m$ против всех известных простых чисел $\leq {\sqrt {m}}$). Тогда перед тестированием $n$ для простоты крупномасштабным методом, $n$можно сначала проверить на делимость на любое простое число из списка. Если оно делится на любое из этих чисел, то оно составное, и любые дальнейшие проверки можно пропустить.

Простой, но очень неэффективный тест на простоту использует теорему Вильсона , которая утверждает, что $p$ является простым тогда и только тогда, когда:

$(p-1)!\equiv -1{\pmod {p}}$

Хотя этот метод требует около $p$ модульные умножения, что делает их непрактичными, теоремы о простых числах и модульных остатках составляют основу многих более практических методов.

Эвристические тесты

Это тесты, которые, кажется, хорошо работают на практике, но не проверены и, следовательно, с технической точки зрения вообще не являются алгоритмами. Тест Ферма и тест Фибоначчи — простые примеры, и они очень в сочетании эффективны. Джон Селфридж предположил, что если p — нечетное число и p ≡ ±2 (по модулю 5), то p будет простым, если выполняются оба следующих условия:

• 2 ^{р -1} ≡ 1 (по модулю p ),
• f _{p +1} ≡ 0 (mod p ),

где fk _k е - – число Фибоначчи . Первое условие — это критерий простоты Ферма по основанию 2.

В общем случае, если p ≡ a (mod x ² +4), где a — квадратичный невычет (mod x ² +4) то p должно быть простым, если выполняются следующие условия:

• 2 ^{р -1} ≡ 1 (по модулю p ),
• ж ( 1 ) _{п ​​+1} ≡ 0 (mod p ),

f ( x ) _k — k - й полином Фибоначчи в точке x .

Селфридж, Карл Померанс и Сэмюэл Вагстафф вместе предлагают 620 долларов за контрпример.

Вероятностные тесты

Вероятностные тесты более строгие, чем эвристики, поскольку они обеспечивают доказуемые границы вероятности быть обманутым составным числом. Многие популярные тесты на простоту являются вероятностными тестами. В этих тестах, помимо проверяемого числа n , используются некоторые другие числа a , которые выбираются случайным образом из некоторого выборочного пространства ; обычные рандомизированные тесты на простоту никогда не сообщают о простом числе как о составном, но составное число может быть указано как простое. Вероятность ошибки можно уменьшить, повторяя тест с несколькими независимо выбранными значениями a ; для двух часто используемых тестов для любого составного n по крайней мере половина составность n a обнаруживает поэтому , k повторений уменьшают вероятность ошибки не более чем до 2 ^{- к} , который можно сделать сколь угодно малым, увеличив k .

Базовая структура рандомизированных тестов на простоту выглядит следующим образом:

1. Случайным образом выберите число a .
2. Проверить равенство (соответствующее выбранному критерию) числа a и заданного числа n . Если равенство не выполняется, то n — составное число, а a — свидетель составности, и тест прекращается.
3. Возвращайтесь к первому шагу, пока не будет достигнута требуемая точность.

Если после одной или нескольких итераций n не окажется составным числом, его можно объявить, вероятно, простым .

Ферма

Самый простой вероятностный тест простоты — это тест простоты Ферма (фактически тест на составность). Это работает следующим образом:

Учитывая целое число n , выберите некоторое целое число, взаимно простое с n , и вычислите ^{н − 1} по модулю н . Если результат отличается от 1, то n составное. Если это 1, то n может быть простым.

Если ​ ^{н −1} (по модулю n ) равно 1, но n не является простым, тогда n называется псевдопростое, чтобы основать . На практике, если а ^{н −1} (по модулю n ) равно 1, то n обычно простое. Но вот контрпример: если n = 341 и a = 2, то

$2^{340}\equiv 1{\pmod {341}}$

хотя 341 = 11·31 является составным. Фактически, 341 — это наименьшее псевдопростое число по основанию 2 (см. рис. 1). ).

Существует только 21853 псевдопростых числа по основанию 2, размер которых меньше 2,5 × 10. ¹⁰ (см. стр. 1005 ). Это означает, что для n до 2,5 × 10 ¹⁰ , если 2 ^{н −1} (по модулю n ) равно 1, то n является простым, если только n не является одним из этих 21853 псевдопростых чисел.

Некоторые составные числа ( числа Кармайкла ) обладают тем свойством, что ^{н − 1} равен 1 (по модулю n ) для каждого a , взаимно простого с n . Самый маленький пример — n = 561 = 3·11·17, для которого ⁵⁶⁰ равно 1 (по модулю 561) для всех чисел , взаимно простых с 561. Тем не менее, тест Ферма часто используется, если необходим быстрый просмотр чисел, например, на этапе генерации ключа криптографического алгоритма с открытым ключом RSA .

Критерий простоты Миллера-Рабина и

Критерий простоты Миллера -Рабина и тест простоты Соловея-Штрассена представляют собой более сложные варианты, которые обнаруживают все составные числа (опять же, это означает: для каждого составного числа n не менее 3/4 (Миллер-Рабин) или 1/2 (Соловей –Штрассен) чисел a являются свидетелями составности n ). Это также тесты на составность.

Критерий простоты Миллера-Рабина работает следующим образом: Учитывая целое число n , выберите некоторое положительное целое число a < n . Пусть 2 ^с d = n − 1, где d нечетно. Если

$a^{d}\not \equiv \pm 1{\pmod {n}}$

и

$a^{2^{r}d}\not \equiv -1{\pmod {n}}$ для всех $0\leq r\leq s-1,$

тогда n составное и a является свидетелем составности. В противном случае n может быть простым, а может и не быть простым. Критерий Миллера-Рабина является сильным вероятностным простым критерием (см. PSW стр. 1004).

Тест на простоту Соловея – Штрассена использует другое равенство: учитывая нечетное число n , выберите некоторое целое число a < n , если

$a^{(n-1)/2}\not \equiv \left({\frac {a}{n}}\right){\pmod {n}}$, где $\left({\frac {a}{n}}\right)$ это символ Якоби ,

тогда n составное и a является свидетелем составности. В противном случае n может быть простым, а может и не быть простым. Критерий Соловея – Штрассена представляет собой тест Эйлера на вероятность простых чисел (см. PSW стр. 1003).

Для каждого отдельного значения критерий Соловея-Штрассена слабее критерия Миллера-Рабина. Например, если n = 1905 и a = 2, то критерий Миллера-Рабина показывает, что n является составным, а критерий Соловея-Штрассена - нет. Это потому, что 1905 год — это Эйлер. псевдопростое основание 2, но не сильное псевдопростое основание 2 (это показано на рисунке 1 PSW ).

Фробениуса

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

Тест Фробениуса является обобщением теста Люка на вероятность простых чисел .

простоту Бэйли-

Тест простоты Бэйли-ПСВ — это вероятностный тест простоты, который сочетает в себе тест Ферма или Миллера-Рабина с тестом вероятного простого числа Лукаса для получения теста простоты, не имеющего известных контрпримеров. То есть не существует известных составных n , для которых этот тест показал бы, что n , вероятно, простое. Показано, что для n нет контрпримеров. $<2^{64}$.

Другие тесты

Леонард Адлеман и Минг-Де Хуанг представили безошибочный (но с ожидаемым полиномиальным временем) вариант теста на простоту эллиптической кривой . В отличие от других вероятностных тестов, этот алгоритм выдает сертификат простоты и, таким образом, может использоваться для доказательства того, что число является простым. На практике алгоритм непомерно медленный.

Если бы были доступны квантовые компьютеры , простоту можно было бы проверять асимптотически быстрее , чем с помощью классических компьютеров. Сочетание алгоритма Шора , метода факторизации целых чисел, с тестом на простоту Поклингтона могло бы решить проблему в $O((\log n)^{3}(\log \log n)^{2}\log \log \log n)$.

Быстрые

Ближе к началу 20-го века было показано, что следствие малой теоремы Ферма можно использовать для проверки простоты. В результате появился тест на простоту Поклингтона . Однако, поскольку этот тест требует частичной факторизации n - 1 , время выполнения в худшем случае все равно было довольно медленным. Первым детерминистическим тестом на простоту, значительно более быстрым, чем наивные методы, был тест циклотомии ; можно доказать, что его время выполнения равно O ((log n ) ^{c журнал журнал журнал n} ), где n — число, которое нужно проверить на простоту, а c — константа, независимая от n . Было сделано множество дальнейших улучшений, но ни одно из них не имело полиномиального времени работы. (Время выполнения измеряется размером входных данных, который в данном случае равен ~ log n , то есть количеству битов, необходимых для представления числа n .) тест на простоту эллиптической кривой Можно доказать, что выполняется за O( (журнал n ) ⁶ ), если некоторые гипотезы аналитической теории чисел верны. Аналогичным образом, согласно обобщенной гипотезе Римана , можно доказать, что детерминированный тест Миллера , который составляет основу вероятностного теста Миллера-Рабина, работает в Õ ((log n ) ⁴ ). На практике этот алгоритм медленнее, чем два других, для чисел, с которыми вообще можно иметь дело. Поскольку реализация этих двух методов довольно сложна и создает риск ошибок программирования, часто предпочитаются более медленные, но более простые тесты.

изобрели первый доказуемо безусловный детерминированный полиномиальный временной тест на простоту В 2002 году Маниндра Агравал , Нирадж Каял и Нитин Саксена . Тест простоты AKS выполняется за Õ((log n ) ¹² ) (улучшено до Õ((log n ) ^7.5 ) в опубликованной версии их статьи), что в дальнейшем можно свести к Õ((log n ) ⁶ ), если гипотеза Софи Жермен верна. Впоследствии Ленстра и Померанс представили версию теста, работающую во времени Õ((log n ) ⁶ ) безоговорочно.

Агравал, Каял и Саксена предлагают вариант своего алгоритма, который будет работать за Õ((log n ) ³ ) если гипотеза Агравала верна; однако эвристический аргумент Хендрика Ленстры и Карла Померанса предполагает, что это, вероятно, неверно. Модифицированная версия гипотезы Агравала, гипотеза Агравала-Поповича, может все еще быть правдой.

Сложность

В теории сложности вычислений формальный язык, соответствующий простым числам, обозначается ПРОСТЫМИ числами. Легко показать, что ПРОСТОЕ находится в Co-NP : его дополнение КОМПОЗИТЫ находится в NP, потому что можно определить составность, недетерминированно угадывая фактор.

В 1975 году Воан Пратт показал, что существует сертификат простоты, который можно проверить за полиномиальное время, и, таким образом, PRIMES находится в NP и, следовательно, в ${\mathsf {NP\cap coNP}}$. см. в сертификате первичности Подробную информацию .

Последующее открытие алгоритмов Соловея-Штрассена и Миллера-Рабина поместило PRIMES в coRP . В 1992 году алгоритм Адлемана – Хуанга уменьшил сложность до ${\mathsf {{\color {Blue}ZPP}=RP\cap coRP}}$, что заменило результат Пратта.

Тест на простоту Адлемана -Померанса-Румели 1983 года поместил ПРОСТОТЫ в QP ( квазиполиномиальное время ), которое, как известно, не сравнимо с классами, упомянутыми выше.

Из-за его практичности, алгоритмов с полиномиальным временем, предполагающих гипотезу Римана, и других подобных доказательств, долгое время подозревалось, но не было доказано, что простота может быть решена за полиномиальное время. Существование теста простоты AKS наконец решило этот давний вопрос и поместило PRIMES в P . Однако неизвестно, является ли PRIMES P-полным , и неизвестно, принадлежит ли он классам, лежащим внутри P таким как NC или L. , Известно, что ПРАЙМСА нет в AC ⁰ .

Теоретико-числовые методы

Существуют определенные теоретико-числовые методы проверки того, является ли число простым, например тест Лукаса и тест Прота . Эти тесты обычно требуют факторизации n + 1, n - 1 или аналогичной величины, что означает, что они бесполезны для общего тестирования простоты, но они часто весьма эффективны, когда тестируемое число n известно, что имеет специальное число. форма.

Тест Люка основан на том факте, что мультипликативный порядок числа a по модулю n равен n - 1 для простого числа n , когда a является примитивным корнем по модулю n . Если мы можем показать, что a является примитивным для n , мы можем показать, что n является простым.

Источники

• Крэндалл, Ричард ; Померанс, Карл (2005). Простые числа: вычислительная перспектива (2-е изд.). Спрингер. ISBN  0-387-25282-7 . Глава 3: Распознавание простых и составных чисел, стр. 109–158. Глава 4: Доказательство первичности, стр. 159–190. Раздел 7.6: Доказательство простоты эллиптических кривых (ECPP), стр. 334–340.
• Кнут, Дональд (1997). «раздел 4.5.4». Искусство компьютерного программирования . Том. 2: Получисловые алгоритмы (3-е изд.). Аддисон-Уэсли. стр. 391–396. ISBN  0-201-89684-2 .
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001). «Раздел 31.8: Тестирование на примитивность». Введение в алгоритмы (второе изд.). MIT Press, МакГроу-Хилл. стр. 887–896. ISBN  0-262-03293-7 .
• Пападимитриу, Христос Х. (1993). «Раздел 10.2: Первичность». Вычислительная сложность (1-е изд.). Эддисон Уэсли. стр. 100-1 222 –227 . ISBN  0-201-53082-1 . Збл   0833.68049 .
• Ризель, Ганс (1994). Простые числа и компьютерные методы факторизации . Прогресс в математике. Том. 126 (второе изд.). Бостон, Массачусетс: Биркхойзер. ISBN  0-8176-3743-5 . №   0821.11001 .

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

• Соловей-Штрассен (computacion.cs.cinvestav.mx) в archive.today (архивировано 20 декабря 2012 г.) - Реализация теста простоты Соловея-Штрассена в Maple
• Отличие простых чисел от составных чисел, DJ Bernstein (cr.yp.to)
• Прайм-страницы (primes.utm.edu)
• Тест Лукаса на простоту с факторизованным N - 1 (MathPages.com) в веб-архивах Библиотеки Конгресса (заархивировано 6 августа 2010 г.)
• PRIMABOINCA — это исследовательский проект, в котором компьютеры, подключенные к Интернету, используются для поиска контрпримеров некоторым гипотезам. Первая гипотеза ( гипотеза Агравала ) послужила основой для формулировки первого детерминированного алгоритма простого теста за полиномиальное время ( алгоритм AKS ).