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

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

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

Доказательство

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

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

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

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

то ${\displaystyle n}$ — простое число.

Доказательство

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

Область применимости

В отличие от теоремы Сэлфриджа, критерий Поклингтона не требует знания полного разложения числа ${\displaystyle n-1}$ на простые сомножители и позволяет ограничиться частичной факторизацией числа ${\displaystyle n-1}$ . Он подходит для проверки на простоту при условии, что ${\displaystyle n-1}$ делится на простое число ${\displaystyle q>{\sqrt {n}}-1}$ , а также если ${\displaystyle q}$ можно найти и доказать его простоту.

Также стоит отметить, что этот критерий является вероятностым только в том смысле, что случайно выбранное число ${\displaystyle a}$ может либо удовлетворять условию НОД ${\displaystyle (a^{(n-1)/q}-1,n)=1}$ , либо не удовлетворять ему. Если ${\displaystyle n=RF+1}$ — нечетное простое число, ${\displaystyle F>{\sqrt {n}}-1}$ , ${\displaystyle F=q_{1}^{\alpha _{1}}q_{2}^{\alpha _{2}}...q_{k}^{\alpha _{k}},}$ НОД ${\displaystyle (R,F)=1}$ то для случайно выбранного числа ${\displaystyle 1<a<n}$ эта вероятность есть ${\displaystyle \prod _{i=1}^{k}(1-{\frac {1}{q_{i}}})}$ . Однако, как только найдено такое ${\displaystyle a}$ , критерий доказывает, что ${\displaystyle n}$ — простое число. В отличие от вероятностных тестов (таких, например, как тест Миллера-Рабина , тест Соловея-Штрассена и др.) заключение теста Поклингтона — вполне определённое.

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

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

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

Пример

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

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

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

Частные случаи

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

Пусть ${\displaystyle n=2^{k}R+1}$ , где ${\displaystyle R<2^{k}}$ , ${\displaystyle Z<2^{k}+1}$ , и ${\displaystyle Z}$ не делит ${\displaystyle R}$ . Тогда ${\displaystyle n}$ — простое число в том и только в том случае, если выполняется условие ${\displaystyle 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