Критерий Поклингтона

Критерий Поклингтона — детерминированный тест на простоту, разработанный Генри Поклингтоном (Henry Cabourn Pocklington) и Деррик Генри Лехмером (Derrick Henry Lehmer). Критерий Поклингтона позволяет определять, является ли данное число простым .

Теорема Поклингтона


 Пусть n=qkR+1 где q - простое число, k1. Если существует такое целое число a , что an11(modn) и НОД(a(n1)/q1,n)=1, то каждый простой делитель p числа a имеет вид p=qkr+1 при некотором натуральном r.

Доказательство теоремы Поклингтона


 Пусть p – простой делитель числа n. Тогда из условия теоремы вытекает, что an1=1(modp) и a(n1)/q1(modp). Отсюда получаем, что порядок m элемента a по модулю p удовлетворяет условиям
n1=md
, где d - некоторое целое. Допустим, q делит d. В этом случае (n1)/q=m(d/q), где (d/q) - целое. Следовательно a(n1)/q=1(modp), что невозможно. Поскольку n1=md=qkR, то m делится на qk. Однако m должно делить число p1 Следовательно,p=qkr+1 при некотором r. Теорема доказана.

Критерий Поклингтона


 Пусть n - натуральное число. Пусть число n1 имеет простой делитель q, причем q>n1. Если найдётся такое целое число a, что выполняются следующие два условия:

  1. an11(modn)
  2. числа n и a(n1)/q1 взаимнопросты,

 то n - простое число.

Доказательство критерия Поклингтона


 Предположим, что n является составным числом. Тогда существует простое число p - делитель n, причем p<n. Заметим, что q>p1, следовательно q и p1 - взаимнопросты. Следовательно, существует некоторое целое число u, такое, что uq1(modp1). Но в таком случае a(n1)/qauq(n1)/q=au(n1)1(modp) (в силу условия 1)). Но таким образом получено противоречие условию 2). Следовательно, n является простым числом.

Замечания к критерию Поклингтона


 В отличие от теоремы Сэлфриджа критерий Поклингтона не требует знания полного разложения числа n1 на простые сомножители и позволяет ограничиться частичной факторизацией числа n1. Он является отличным тестом на простоту при условии, что n1 делится на простое число q>n1, а также если q можно найти и доказать его простоту. Иначе, этим критерием пользоваться нельзя. Также стоит отметить, что этот критерий является вероятностым только в том смысле, что случайно выбранное число a может либо удовлетворять условию НОД\textbf'' $(a^{(n-1)/q -1, n) = 1,либонеудовлетворятьему.Еслиn=RF+1нечетноепростоечисло,F > \sqrt{n - 1,F = q_1^{\alpha_1}q_2^{\alpha_2}...q_k^{\alpha_k}$ , НОД (R,F)=1 то для случайно выбранного числа 1<a<n эта вероятность есть i=1k(11qi). Однако, как только найдено такое a, критерий доказывает, что n - простое число. В отличие от вероятностных тестов (таких, например, как тест Миллера-Рабина, тест Соловея-Штрассена и др.) заключение теста Поклингтона - вполне определенное.
 Наибольшей трудностью связанной с использованием данного критерия может являться необходимость нахождения простого делителя числа n1, что может свестись на практике к полной факторизации. Нахождение подходящего a – менее сложная задача.  Согласно Нилу Коблицу, значение a=2 часто подходит для проверки критерием Поклингтона.

Оценка вычислительной сложности теста Поклингтона


 Хотя тест Поклингтона и позволяет доказать лишь то, что число n является простым при верно выбранном a, можно оценить его алгоритмическую сложность в предположении, что мы выбрали его верно. Вычислительная сложность теста будет складываться из сложности факторизации числа n и числа a(n1)/q1. При использовании алгоритмов факторизации с субэкспоненциальной сложностью её можно ограничить сверху величиной Lan[α,c] обозначенной в L-нотации, где α и c зависят от выбора алгоритма факторизации.

Пример


 Докажем, что число n=31 является простым. Найдём простой делитель числа n1, т.е. 30. Им является q=5, причём 5>311. Число a=2 удовлетворяет обоим критериям:

  1. 2301(mod31)
  2. числа 31 и 2(311)/51 взаимнопросты,

 Следовательно число 31 простое по критерию Поклингтона

Частные случаи критерия Поклингтона


 Частным случаем критерия Поклингтона является теорема Прота, являющаяся тестом простоты для чисел Прота n=2kR+1, где R – нечётно иR<2k. Она имеет следующий вид:
 Пусть n=2kR+1, где R<2k, Z<2k+1, и Z не делит R. Тогда n – простое число в том и только в том случае, если выполняется условие Z(n1)/2=1(modn).

См также



  • Тест простоты
  • Тест Соловея — Штрассена
  • Тест Миллера — Рабина