Тест на первичность - Primality test

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

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

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

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

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

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

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

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

Обратите внимание на то, что продукты старше 10  ×  10 просто повторяют числа, которые встречались в более ранних продуктах. Например, 5  ×  20 и 20  ×  5 состоят из одинаковых чисел. Это верно для всех n : все уникальные делители n являются числами, меньшими или равными n , поэтому нам не нужно искать за этим. (В этом примере 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 простое тогда и только тогда, когда:

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

Пример кода

Python

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

def is_prime(n: int) -> bool:
    """Primality test using 6k+-1 optimization."""
    if n <= 3:
        return n > 1
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i ** 2 <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

C #

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

bool IsPrime(int n)
{
    if (n == 2 || n == 3)
        return true;

    if (n <= 1 || n % 2 == 0 || n % 3 == 0)
        return false;

    for (int i = 5; i * i <= n; i += 6)
    {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }

    return true;
}

JavaScript

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

function isPrime(num) {
  if (num <= 3) return num > 1;
  
  if ((num % 2 === 0) || (num % 3 === 0)) return false;
  
  let count = 5;
  
  while (Math.pow(count, 2) <= num) {
    if (num % count === 0 || num % (count + 2) === 0) return false;
    
    count += 6;
  }
  
  return true;
}

р

Ниже приведен тест на простоту на R (язык программирования) с использованием той же оптимизации, что и выше.

is.prime <- function(number) {
  if(number <= 1 || number %% 2 ==0 || number %% 3 == 0) {
    return (FALSE)
  } else if (number == 2 || number == 3 ) {
    return(TRUE)
  }
  i <- 5
  while (i*i <= number) {
    if(number %% i == 0 || number %% (i+2)==0) {
      return(FALSE)
    } else {
      return(TRUE)
    }
    i = i + 6
  }
  return(TRUE)
}

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

Это тесты, которые кажутся хорошо работающими на практике, но недоказанными и, следовательно, с технической точки зрения вообще не являются алгоритмами. Тест Ферма и тест Фибоначчи - простые примеры, и они очень эффективны в сочетании. Джон Селфридж предположил, что если 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 г.

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

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

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

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

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

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

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

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

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

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

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

Некоторые составные числа ( номер Carmichael ) обладают свойством , что в п - 1 является 1 ( по модулю п ) для каждого а , который взаимно прост с п . Маленький пример п = 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, стр. 1004).

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

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

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

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

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

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

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

Тест на простоту Baillie-PSW

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

Другие тесты

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

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

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

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

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

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

Сложность

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

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

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

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

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

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

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

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

использованная литература

Источники

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