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

Алгоритм определения того, является ли число простым

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

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

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

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

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

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

${\displaystyle 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}$.

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

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

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

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

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

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

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

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

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

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

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

Пример кода

Тесты на простоту могут быть реализованы различными способами. Вот примеры на разных языках программирования :

Питон

Этот тест выполняется на Python с использованием простой оптимизации 6 k ± 1, упомянутой ранее. Более сложные методы, описанные ниже, работают намного быстрее для больших n .

из  математического  импорта  isqrtdef  is_prime ( n :  int )  ->  bool : если  n  <=  3 : вернуть  n  >  1 если  n  %  2  ==  0  или  n  %  3  ==  0 : вернуть  ложь предел  =  isqrt ( n ) для  i  в  диапазоне ( 5 ,  предел + 1 ,  6 ): если  n  %  i  ==  0  или  n  %  ( i + 2 )  ==  0 : вернуть  ложь вернуть  истину

С, С++, С#, Д

Этот тест относится к семейству языков с фигурными скобками C и использует ту же оптимизацию, что и выше.

bool IsPrime ( int n )  { если ( п == 2 || п == 3 )        вернуть истину ;  если ( n <= 1 || n % 2 == 0 || n % 3 == 0 )                вернуть ложь ;  для ( int я знак равно 5 ; я * я <= n ; я += 6 )             { если ( n % я == 0 || n % ( я + 2 ) == 0 )              вернуть ложь ;  } вернуть истину ; }

OCaml

Этот тест выполнен в OCaml .

пусть  is_prime  n  = если  n  <=  1  , то ЛОЖЬ еще ( если  n  =  2  ||  n  =  3  , то истинный еще ( если  n  mod  2  =  0  ||  n  mod  3  =  0  , то ЛОЖЬ еще пусть  я  =  ссылка  5  в пока  ! я  *  ! я  <=  n  &&  n  мод  ! я  <>  0  &&  n  mod  (! i  +  2 )  <>  0  делать я  :=  ! я  +  6 сделанный ; (! я  *  ! я  >  п ) ) )

Ржавчина

Этот тест проводится на Rust с использованием той же оптимизации, что и выше.

fn  is_prime ( n : i32 )  -> bool  { если n == 2 || п == 3 {         вернуть истину ;  } если n <= 1 || п % 2 == 0 || п % 3 == 0 {                 вернуть ложь ;  }  для меня в ( 5 .. ). шаг_по ( 6 ). take_ while ( | я | я * я <= n ) {          если n % i == 0 || п % ( я + 2 ) == 0 {               вернуть ложь ;  } } истинный}

Джава

Этот тест выполнен на Java с использованием той же оптимизации, что и выше.

импортировать java.util.* ; public static boolean isPrime ( int n ){      если ( п <= 1 )    вернуть ложь ;   если ( п == 2 || п == 3 )        вернуть истину ;   если ( n % 2 == 0 || n % 3 == 0 )            вернуть ложь ;   for ( int я знак равно 5 ; я <= Math . sqrt ( n ); я знак равно я + 6 )             если ( n % я == 0 || n % ( я + 2 ) == 0 )              вернуть ложь ;  вернуть истину ; }

JavaScript

Этот тест выполнен на JavaScript с использованием той же оптимизации, что и выше.

функция isPrime ( число ) {   если ( число == 2 || число == 3 )        вернуть истину ;  if ( num <= 1 || num % 2 == 0 || num % 3 == 0 )                вернуть ложь ;   for ( пусть я знак равно 5 ; я * я <= число ; я += 6 ) {             if ( num % i == 0 || num % ( i + 2 ) == 0 )              вернуть ложь ;  } вернуть истину ; }

р

Этот тест проводится на R с использованием той же оптимизации, что и выше.

is.prime <- функция ( число ) {    если ( число <= 1 ) {    возврат ( ЛОЖЬ ) } еще если ( число <= 3 ) {      возврат ( ИСТИНА ) } if ( число %% 2 == 0 || число %% 3 == 0 ) {            возврат ( ЛОЖЬ ) } я <- 5   while ( я * я <= число ) {    if ( число %% я == 0 || число %% ( я +2 ) == 0 ) {            возврат ( ЛОЖЬ ) } я = я + 6     } возврат ( ИСТИНА )}

Дарт

Этот тест проводится в Dart с использованием той же оптимизации, что и выше.

checkIfPrimeNumber ( число ) {  если ( число == 2 || число == 3 ) {         вернуть «истину» ;  } else if ( число <= 1 || число % 2 == 0 || число % 3 == 0 ) {                   вернуть «ложь» ;  } for ( int я знак равно 5 ; я * я <= число ; я += 6 ) {              if ( число % я == 0 || число % ( я + 2 ) == 0 ) {               вернуть «ложь» ;  } } вернуть «истину» ; }

Бесплатный Паскаль

Этот тест проводится в Free Pascal с использованием той же оптимизации, что и выше.

функция IsPrime ( N : Int64 ) : Boolean ;  вар Я : Int64 ; начинать если (( N = 2 ) или ( N = 3 )) то         Выход ( Истина ) ; если (( N <= 1 ) или (( N mod 2 ) = 0 ) или (( N mod 3 ) = 0 )) то                 Выход ( Ложь ) ; Я := 5 ;   пока ( I * I <= N ) делаю       начинать если (( N mod I ) = 0 ) или (( N mod ( I + 2 )) = 0 ) , то               Выход ( Ложь ) ; Инк ( я , 6 ) ;  конец ; Выход ( Истина ) ;конец ;

Идти

Этот тест выполнен на Go с той же оптимизацией, что и выше.

func IsPrime ( num int ) bool {    если число > 1 && число <= 3 {        вернуть истину }если число <= 1 || число % 2 == 0 || число % 3 == 0 {            вернуть ложь }для я := 5 ; я * я <= число ; я += 6 {          если число % я == 0 || число % ( я + 2 ) == 0 {        вернуть ложь }}вернуть истину }

Хаскелл

Этот тест выполнен на Haskell с использованием той же оптимизации, что и выше.

isPrime :: Int -> Bool    isPrime = go $ 2 : 3 : scanl ( + ) 5 ( цикл [ 2 , 4 ])              где иди ( п : пс ) н   | р * р > n = Истина        | n ` mod ` p == 0 = Ложь        | иначе = идти PS n     

Регулярное выражение

Простой метод также можно выполнить с использованием регулярного выражения , создав строку из n одинаковых символов и запустив выражение вида:

/^.?$|^(..+?)\1+$/

Если выражение совпадает, число не является простым числом.

Выражение состоит из двух ветвей:

• Первая ветвь соответствует 0 и 1.
• Вторая ветвь проверит, существует ли какая-либо последовательность из 2 или более символов, которая повторяется целое число раз, начиная с наименьшей последовательности и увеличивая ее. (Квантор +?является ленивым квантификатором , то есть он будет пытаться сопоставить как можно меньше символов, увеличивая размер только в том случае, если не найдено совпадений с использованием этого значения).

Хотя это компактная проверка, она выполняет менее эффективную версию, в которой проверяются все возможные делители от 2 до n , не останавливаясь на . ${\displaystyle {\sqrt {n}}}$

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

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

• 2 ^{p −1} ≡ 1 (mod p ),
• f _{p +1} ≡ 0 (mod p ),

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

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

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

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

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

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

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

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

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

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

Тест на простоту Ферма

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

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

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

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

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

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

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

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

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

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

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

и

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

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

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

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

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

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

Тест на простоту Фробениуса

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

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

Тест на простоту Бэйли – PSW

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

Другие тесты

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

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

Быстрые детерминированные тесты

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

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

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

Сложность

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

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

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

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

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

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

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

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

Рекомендации

1. Ризель (1994), стр.2-3.
2. Джон Селфридж#Гипотеза Селфриджа о тестировании на простоту .
3. Померанс, Карл ; Селфридж, Джон Л .; Вагстафф, Сэмюэл С. младший (июль 1980 г.). «Псевдопростые числа до 25·109» (PDF) . Математика вычислений . 35 (151): 1003–1026. дои : 10.1090/S0025-5718-1980-0572872-7 .
4. Бэйли, Роберт; Вагстафф, Сэмюэл С. младший (октябрь 1980 г.). «Лукас Псевдопраймс» (PDF) . Математика вычислений . 35 (152): 1391–1417. дои : 10.1090/S0025-5718-1980-0583518-6 . МР  0583518.
5. Бэйли, Роберт; Фиори, Эндрю; Вагстафф, Сэмюэл С. младший (июль 2021 г.). «Усиление теста на первичность Бэйли-PSW». Математика вычислений . 90 (330): 1931–1955. arXiv : 2006.14425 . дои : 10.1090/mcom/3616. S2CID  220055722.
6. Адлеман, Леонард М .; Хуан, Мин-Де (1992). Проверка простоты и абелевы многообразия над конечным полем . Конспекты лекций по математике. Том. 1512. Шпрингер-Верлаг . ISBN 3-540-55308-8.
7. Чау, ХФ; Ло, Х.-К. (1995). «Тест на простоту посредством квантовой факторизации». arXiv : Quant-ph/9508005 .
8. Поклингтон, ХК (1914). «Определение простой или составной природы больших чисел по теореме Ферма». Камбр. Фил. Соц. Проц . 18 :29–30. ЖФМ  45.1250.02.
9. Вайсштейн, Эрик В. «Теорема Поклингтона». Математический мир .
10. Гэри Л. Миллер (1976). «Гипотеза Римана и тесты на первичность». Журнал компьютерных и системных наук . 13 (3): 300–317. дои : 10.1016/S0022-0000(76)80043-8 .
11. Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (2004). «Простые числа находятся в P» (PDF) . Анналы математики . 160 (2): 781–793. дои : 10.4007/анналы.2004.160.781 .
12. Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (2004). «ПРАЙМС находится в P» (PDF) . Анналы математики . 160 (2): 781–793. дои : 10.4007/анналы.2004.160.781 .
13. Карл Померанс и Хендрик В. Ленстра (20 июля 2005 г.). «Тестирование простоты с гауссовскими периодами» (PDF) .
14. Попович, Роман (30 декабря 2008 г.). «Заметка о гипотезе Агравала» (PDF) .
15. Э. Аллендер, М. Сакс и И.Е. Шпарлинский, Нижняя оценка простоты, J. Comp. Сист. наук. 62 (2001), стр. 356–366.

Источники

• Крэндалл, Ричард ; Померанс, Карл (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-е изд.). Эддисон Уэсли. стр. 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 ).