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

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

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

Пусть ${\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