Processing math: 100%

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

Критерий Поклингтона — детерминированный тест на простоту,разработанный Генри Поклингтоном (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 этавероятность есть ki=1(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).

См также



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