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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Теорема Поклингтона[править | править вики-текст]

Пусть n = q^k * R + 1 где q - простое число, k \geqslant 1. Если существует такое целое число a , что a^{n-1} \equiv 1 \pmod n и НОД(a^{{(n-1)}/q} - 1, n) = 1, то каждый простой делитель p числа a имеет вид p = q^kr + 1 при некотором натуральном r

Доказательство теоремы Поклингтона[править | править вики-текст]

Пусть p – простой делитель числа n. Тогда из условия теоремы вытекает, что  a^{n-1} = 1\pmod{p} и  a^{(n-1)/q} \neq 1 \pmod{p}. Отсюда получаем, что порядок m элемента a по модулю p удовлетворяет условиям:n-1 = md, где d - некоторое целое. Допустим, q делит d. В этом случае (n-1)/q=m(d/q), где (d/q) - целое. Следовательно a^{(n-1)/q} = 1\pmod{p}, что невозможно. Поскольку n-1=md=q^kR, то m делится на q^k. Однако m должно делить число p-1 Следовательно,p=q^kr+1 при некотором r. Теорема доказана.

Критерий Поклингтона[править | править вики-текст]

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

  1. a^{n-1} \equiv 1 \pmod n
  2. числа n и ~a^{(n-1)/q} -1 взаимнопросты,

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

Доказательство критерия Поклингтона[править | править вики-текст]

Предположим, что n является составным числом. Тогда существует простое число p - делитель n, причем p < \sqrt {n} . Заметим, что q > p -1 , следовательно q и p-1 - взаимнопросты. Следовательно, существует некоторое целое число u, такое, что uq \equiv 1 \pmod{p-1}. Но в таком случае ~a^{(n-1)/q}\equiv a^{uq(n-1)/q} =  a^{u(n-1)}\equiv 1 \pmod p (в силу условия 1)). Но таким образом получено противоречие условию 2). Следовательно, n является простым числом.

Замечания к критерию Поклингтона[править | править вики-текст]

В отличие от теоремы Сэлфриджа критерий Поклингтона не требует знания полного разложения числа n-1 на простые сомножители и позволяет ограничиться частичной факторизацией числа n-1. Он является отличным тестом на простоту при условии, что n-1 делится на простое число q > \sqrt {n} -1 , а также если q можно найти и доказать его простоту. Иначе, этим критерием пользоваться нельзя. Также стоит отметить, что этот критерий является вероятностым только в том смысле, что случайно выбранное число a может либо удовлетворять условию НОД ~(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 эта вероятность есть \prod_{i=1}^k(1-\frac{1}{q_i}). Однако, как только найдено такое a, критерий доказывает, что n - простое число. В отличие от вероятностных тестов (таких, например, как тест Миллера-Рабина, тест Соловея-Штрассена и др.) заключение теста Поклингтона - вполне определенное.

Наибольшей трудностью связанной с использованием данного критерия может являться необходимость нахождения простого делителя числа n-1, что может свестись на практике к полной факторизации. Нахождение подходящего a – менее сложная задача.  Согласно Нилу Коблицу, значение  a = 2 часто подходит для проверки критерием Поклингтона.

Оценка вычислительной сложности теста Поклингтона[править | править вики-текст]

Хотя тест Поклингтона и позволяет доказать лишь то, что число n является простым при верно выбранном a, можно оценить его алгоритмическую сложность в предположении, что мы выбрали его верно. Вычислительная сложность теста будет складываться из сложности факторизации числа n и числа ~a^{(n-1)/q} -1 . При использовании алгоритмов факторизации с субэкспоненциальной сложностью её можно ограничить сверху величиной L_{a^n}[\alpha,c] обозначенной в L-нотации, где \alpha и c зависят от выбора алгоритма факторизации.

Пример[править | править вики-текст]

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

  1. 2^{30} \equiv 1 \pmod {31}
  2. числа  31 и ~2^{(31-1)/5} -1 взаимнопросты,

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

Частные случаи критерия Поклингтона[править | править вики-текст]

Частным случаем критерия Поклингтона является теорема Прота, являющаяся тестом простоты для чисел Прота n=2^{k}R+1, где R – нечётно иR<2^{k}. Она имеет следующий вид:

Пусть n=2^{k}R+1, где R<2^k,  Z < 2^k + 1, и Z не делит R. Тогда n – простое число в том и только в том случае, если выполняется условие  Z^{(n - 1)/2} = -1 \pmod{n}.

См также[править | править вики-текст]

Литература[править | править вики-текст]

  1. Н. Коблиц, Курс теории чисел и криптографии ISBN 5-94057-103-4
  2. Ю.В.Романец, П.А.Тимофеев, В.Ф.Шаньгин, Защита информации в компьютерных системах и сетях. 2-е изд, ISBN 5-256-01518-4
  3. А.В.Черемушкин, Лекции по арифметическим алгоритмам в криптографии ISBN 5-94057-060-7