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

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

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

Пусть $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$ числа $n$ имеет вид $p=q^{k}r+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^{k}R$ , то $m$ делится на $q^{k}$ . Однако $m$ должно делить число $p-1$ Следовательно, $p=q^{k}r+1$ при некотором $r$ . Теорема доказана.

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

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

$a^{n-1}\equiv 1{\pmod {n}}$
числа $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 удовлетворяет обоим критериям:

$2^{30}\equiv 1{\pmod {31}}$
числа $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}}$ .

См. также

Литература

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.