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

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

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

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

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

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

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

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

1. $a^{n-1}\equiv 1(\mathrm{mod}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(\mathrm{mod}p-1)$. Но в таком случае $a^{(n-1)/q}\equiv a^{uq(n-1)/q}=a^{u(n-1)}\equiv 1(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}n)$.

См. также

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

Литература

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