Из Википедии, бесплатной энциклопедии
  (Перенаправлено из тестирования Primality )
Перейти к навигации Перейти к поиску

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

Простые методы [ править ]

Простейшим тестом на простоту является пробное деление : учитывая введенное число n , проверьте, делится ли оно без остатка на любое простое число от 2 до √ n (т.е. что при делении не остается остатка ). Если да, то п является композитом . В противном случае он прост . [1]

Например, рассмотрим число 100, которое без остатка делится на эти числа:

2, 4, 5, 10, 20, 25, 50

Обратите внимание, что наибольший множитель, 50, равен половине 100. Это верно для всех n : все делители меньше или равны n / 2 .

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

2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2

Обратите внимание на то, что продукты выше 10 x 10 просто повторяют числа, которые были в предыдущих продуктах. Например, 5 x 20 и 20 x 5 состоят из одинаковых чисел. Это верно для всех n : все уникальные делители n являются числами, меньшими или равными √ n , поэтому нам не нужно искать за этим. [1] (В этом примере √ n = √ 100 = 10.)

Все четные числа больше 2 также могут быть исключены, поскольку, если четное число может делить n , то может и 2.

Давайте воспользуемся пробным делением, чтобы проверить простоту числа 17. Нам нужно проверить только делители до √ n , то есть целые числа, меньшие или равные , а именно 2, 3 и 4. Мы можем пропустить 4, потому что это четное число: if 4 может равномерно разделить 17, 2 тоже, а 2 уже есть в списке. Остается 2 и 3. Мы делим 17 на каждое из этих чисел и обнаруживаем, что ни одно из них не делит 17 равномерно - оба деления оставляют остаток. Итак, 17 - простое число.

Мы можем улучшить этот метод и дальше. Обратите внимание, что все простые числа больше 3 имеют форму 6 k  ± 1 , где k - любое целое число больше 0. Это потому, что все целые числа могут быть выражены как (6 k  +  i ) , где i = −1, 0, 1 , 2, 3 или 4. Обратите внимание, что 2 делит (6 k  + 0), (6 k  + 2) и (6 k  + 4), а 3 делит (6 k  + 3) . Итак, более эффективный метод - проверить, делится ли n на 2 или 3, а затем проверить все числа в форме. Это в 3 раза быстрее, чем проверка всех чисел до √ n .

Обобщая далее, все простые числа больше, чем c # ( примитив c ), имеют форму c # · k + i , для i  <  c #, где c и k - целые числа, а i представляет числа, взаимно простые с c # . Например, пусть c  = 6 . Тогда c # = 2 · 3 · 5 = 30 . Все целые числа имеют вид 30 k  +  i для i  = 0, 1, 2, ..., 29 и kцелое число. Однако 2 делит 0, 2, 4, ..., 28; 3 делит 0, 3, 6, ..., 27; и 5 делит 0, 5, 10, ..., 25. Таким образом, все простые числа больше 30 имеют форму 30 k  +  i для i  = 1, 7, 11, 13, 17, 19, 23, 29 (т. е. для i  <30 таких, что gcd ( i , 30) = 1 ). Обратите внимание, что если i и 30 не были взаимно простыми, то 30 k  +  iделится на простой делитель 30, а именно на 2, 3 или 5, и поэтому не будет простым. (Примечание. Не все числа, удовлетворяющие указанным выше условиям, являются простыми. Например: 437 имеет форму c # k + i для c # (7) = 210, k = 2, i = 17. Однако 437 является составным число, равное 19 * 23).

При c  → ∞ количество значений, которые c # k  +  i может принимать в определенном диапазоне, уменьшается, и поэтому время проверки n уменьшается. Для этого метода также необходимо проверить делимость на все простые числа, меньшие c . Наблюдения, аналогичные предыдущим, могут быть применены рекурсивно , давая Решето Эратосфена .

Хороший способ ускорить эти методы (и все другие, упомянутые ниже) - это предварительно вычислить и сохранить список всех простых чисел до определенной границы, скажем, всех простых чисел до 200 (такой список можно вычислить с помощью Решетом Эратосфена или алгоритмом, который проверяет каждое приращение m по всем известным простым числам < √ m ). Затем, прежде чем проверять n на простоту серьезным методом, сначала можно проверить n на делимость на любое простое число из списка. Если он делится на любое из этих чисел, то он составной, и любые дальнейшие тесты можно пропустить.

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

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

Код Python [ править ]

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

def  is_prime ( n :  int )  ->  bool :  "" "Тест на простоту с использованием оптимизации 6k + -1." ""  if  n  <=  3 :  return  n  >  1  if  n  %  2  ==  0  or  n  %  3  ==  0 :  вернуть  False  i  =  5,  а  i  **  2  <=  n :  если  n  %  i  ==  0  или  n  %  (i  +  2 )  ==  0 :  вернуть  False  i  + =  6  вернуть  True

Код C # [ править ]

Ниже приведен тест на простоту в C # с использованием той же оптимизации, что и выше.

bool  IsPrime ( int  n ) {  if  ( n . Equals ( 2 )  ||  n . Equals ( 3 ))  {  return  true ;  }  else  if  ( n  <=  1  ||  ( n  %  2 ). Equals ( 0 )  ||  ( n  %  3 ). Equals ( 0 ))  {  return  false ; }  int  я  =  5 ;  while  ( Math . Pow ( i ,  2 )  <=  n )  {  if  (( n  %  i ). Equals ( 0 )  ||  ( n  %  ( i  +  2 )). Equals ( 0 ))  {  return  false ;  }  я  + =  6 ;  }  вернуть  истину ; }

Код JavaScript [ править ]

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

функция  isPrime ( num )  {  if  ( num  <=  3 )  return  num  >  1 ;  если  (( число  %  2  ===  0 )  ||  ( число  %  3  ===  0 ))  return  false ;  пусть  count  =  5 ;  while  ( Math . pow ( count ,  2 )  <=  num )  {  if  ( num  %  count  ===  0  ||  num  %  ( count  +  2 )  ===  0 )  return  false ;  count  + =  6 ;  }  вернуть  истину ; }

Эвристические тесты [ править ]

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

  • 2 p −1 1 (mod p ),
  • f p +1 ≡ 0 (mod p ),

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

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

  • 2 p −1 1 (mod p ),
  • f ( 1 ) p +1 ≡ 0 (mod p ),

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

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

Вероятностные тесты [ править ]

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

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

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

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

Тест на простоту Ферма [ править ]

Простейшим вероятностным тестом на простоту является тест на простоту Ферма (на самом деле тест на составность). Это работает следующим образом:

Дано целое число п , выбрать некоторое целое число в копервичных к п и вычислить с п - 1 по модулю п . Если результат отличается от 1, то n составное. Если это 1, то n может быть простым.

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

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

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

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

Тест на простоту Миллера – Рабина и Соловея – Штрассена [ править ]

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

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

а также

для всех

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

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

, где - символ Якоби ,

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

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

Тест на простоту Фробениуса [ править ]

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

Тест Фробениуса является обобщением теста псевдопроста Лукаса .

Тест простоты Baillie-PSW [ править ]

Тест на простоту Бэйлей-PSW является вероятностным тестом простоты чисел , который сочетает в себе тест Ферма или Миллер-Рабин с вероятным премьером Лукасом тестом , чтобы пройти тест , который имеет простоту не известные контрпримеры. То есть не существует известного составного числа n, для которого этот тест сообщает, что n , вероятно, является простым. [4] Было показано, что для n нет контрпримеров .

Другие тесты [ править ]

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

Если бы были доступны квантовые компьютеры , простоту можно было бы тестировать асимптотически быстрее, чем с помощью классических компьютеров. Комбинация алгоритма Шора , метода целочисленной факторизации, с тестом на простоту Поклингтона может решить проблему в . [6]

Быстрые детерминированные тесты [ править ]

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

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

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

Сложность [ править ]

В теории сложности вычислений формальный язык, соответствующий простым числам, обозначается как PRIMES. Легко показать, что PRIMES находится в Co-NP : его дополнение COMPOSITES находится в NP, потому что можно определить составность, недетерминированно угадав фактор.

В 1975 году Воан Пратт показал, что существует сертификат простоты, который можно проверить за полиномиальное время, и, таким образом, PRIMES находится в NP и, следовательно, в NP ∩ coNP . См. Подробности в сертификате первичности .

Последующее открытие алгоритмов Соловея – Штрассена и Миллера – Рабина поместило PRIMES в coRP . В 1992 году алгоритм Адлемана – Хуанга [5] снизил сложность до ZPP = RP  ∩  coRP , что заменило результат Пратта.

Тест на простоту Адлеман-Померанс-Rumely от 1983 положить PRIMES в QP ( квазиполиное время ), который не известен, что сравним с классами , упомянутыми выше.

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

Теоретико-числовые методы [ править ]

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

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

Ссылки [ править ]

  1. ^ a b Ризель (1994), стр. 2-3
  2. ^ Гипотеза Джона Селфриджа # Селфриджа о проверке первичности .
  3. ^ a b c d e Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф младший (июль 1980 г.). «Псевдопреступности до 25 · 10 9 » (PDF) . Математика вычислений . 35 (151): 1003–1026. DOI : 10.1090 / S0025-5718-1980-0572872-7 .
  4. ^ Роберт Бэйли; Сэмюэл С. Вагстафф-младший (октябрь 1980 г.). "Лукас Псевдопреступления" (PDF) . Математика вычислений . 35 (152): 1391–1417. DOI : 10.1090 / S0025-5718-1980-0583518-6 . Руководство по ремонту 0583518 .  
  5. ^ а б Адлеман, Леонард М .; Хуанг, Мин-Дэ (1992). Проверка примитивности и абелевы многообразия над конечным полем . Конспект лекций по математике. 1512 . Springer-Verlag . ISBN 3-540-55308-8.
  6. ^ Чау, ВЧ; Ло, Х.-К. (1995). «Проверка первичности с помощью квантовой факторизации». arXiv : квант-ph / 9508005 .
  7. ^ Pocklington, HC (1914). «Определение простого или составного характера больших чисел по теореме Ферма». Cambr. Фил. Soc. Proc . 18 : 29–30. JFM 45.1250.02 . 
  8. ^ Вайсштейн, Эрик В. «Теорема Поклингтона» . MathWorld .
  9. ↑ Гэри Л. Миллер (1976). «Гипотеза Римана и тесты на примитивность». Журнал компьютерных и системных наук . 13 (3): 300–317. DOI : 10.1016 / S0022-0000 (76) 80043-8 .
  10. ^ а б Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин. «Простые числа в букве P» (PDF) . Анналы математики . DOI : 10.4007 / анналы.2004.160.781 .
  11. ^ Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (2004). "ПРИМЕР в П" (PDF) . Анналы математики . 160 (2): 781–793. DOI : 10.4007 / анналы.2004.160.781 .
  12. ↑ Карл Померанс и Хендрик В. Ленстра (20 июля 2005 г.). «Проверка на простоту с гауссовскими периодами» (PDF) .
  13. ^ Попович, Роман (30 декабря 2008). «Заметка о гипотезе Агравала» (PDF) .
  14. ^ Э. Аллендер, М. Сакс и И. Е. Шпарлински, Нижняя оценка простоты, J. Comp. Syst. Sci. 62 (2001), стр. 356–366.

Источники [ править ]

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

Внешние ссылки [ править ]

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