Русская Википедия:Критерий Поклингтона
Критерий Поклингтона — детерминированный тест на простоту, разработанный Шаблон:Нп5 и Дерриком Генри Лехмером. Критерий Поклингтона позволяет определять, является ли данное число простым.
Теорема Поклингтона
Пусть <math>n = q^k R + 1</math> где q — простое число, <math>k \geqslant 1</math>. Если существует такое целое число <math>a</math>, что <math>a^{n-1} \equiv 1 \pmod n</math> и НОД<math>(a^{{(n-1)}/q} - 1, n) = 1</math>, то каждый простой делитель <math>p</math> числа <math>n</math> имеет вид <math>p = q^kr + 1</math> при некотором натуральном <math>r</math>.
Доказательство
Пусть <math>p</math> — простой делитель числа <math>n</math>. Тогда из условия теоремы вытекает, что <math> a^{n-1} = 1\pmod{p}</math> и <math> a^{(n-1)/q} \neq 1 \pmod{p}</math>. Отсюда получаем, что порядок <math>m</math> элемента <math>a</math> по модулю <math>p</math> удовлетворяет условиям:<math>n-1 = md</math>, где <math>d</math> — некоторое целое. Допустим, <math>q</math> делит <math>d</math>. В этом случае <math>(n-1)/q=m(d/q)</math>, где <math>(d/q)</math> — целое. Следовательно <math>a^{(n-1)/q} = 1\pmod{p}</math>, что невозможно. Поскольку <math>n-1=md=q^kR</math>, то <math>m</math> делится на <math>q^k</math>. Однако <math>m</math> должно делить число <math>p-1</math> Следовательно,<math>p=q^kr+1</math> при некотором <math>r</math>. Теорема доказана.
Критерий Поклингтона
Пусть <math>n</math> — натуральное число. Пусть число <math>n-1</math> имеет простой делитель <math>q</math>, причем <math>q > \sqrt {n} -1 </math>. Если найдётся такое целое число <math>a</math>, что выполняются следующие два условия:
- <math>a^{n-1} \equiv 1 \pmod n</math>
- числа <math>n</math> и <math>a^{(n-1)/q} -1 </math> взаимнопросты,
то <math>n</math> — простое число.
Доказательство
Предположим, что <math>n</math> является составным числом. Тогда существует простое число <math>p</math> — делитель <math>n</math>, причем <math>p < \sqrt {n} </math>. Заметим, что <math>q > p -1 </math>, следовательно <math>q</math> и <math>p-1</math> — взаимнопросты. Следовательно, существует некоторое целое число <math>u</math>, такое, что <math>uq \equiv 1 \pmod{p-1}</math>. Но в таком случае <math>a^{(n-1)/q}\equiv a^{uq(n-1)/q} = a^{u(n-1)}\equiv 1 \pmod p</math> (в силу условия 1)). Но таким образом получено противоречие условию 2). Следовательно, <math>n</math> является простым числом.
Область применимости
В отличие от теоремы Сэлфриджа, критерий Поклингтона не требует знания полного разложения числа <math>n-1</math> на простые сомножители и позволяет ограничиться частичной факторизацией числа <math>n-1</math>. Он подходит для проверки на простоту при условии, что <math>n-1</math> делится на простое число <math>q > \sqrt {n} -1 </math>, а также если <math>q</math> можно найти и доказать его простоту.
Также стоит отметить, что этот критерий является вероятностым только в том смысле, что случайно выбранное число <math>a</math> может либо удовлетворять условию НОД <math>(a^{(n-1)/q} -1, n) = 1 </math>, либо не удовлетворять ему. Если <math>n=RF+1</math> — нечетное простое число, <math>F > \sqrt{n} - 1</math>, <math>F = q_1^{\alpha_1}q_2^{\alpha_2}...q_k^{\alpha_k},</math> НОД <math>(R, F)=1</math> то для случайно выбранного числа <math> 1 < a < n</math> эта вероятность есть <math>\prod_{i=1}^k(1-\frac{1}{q_i})</math>. Однако, как только найдено такое <math>a</math>, критерий доказывает, что <math>n</math> — простое число. В отличие от вероятностных тестов (таких, например, как тест Миллера-Рабина, тест Соловея-Штрассена и др.) заключение теста Поклингтона — вполне определённое.
Наибольшей трудностью связанной с использованием данного критерия может являться необходимость нахождения простого делителя числа <math>n-1</math>, что может свестись на практике к полной факторизации. Нахождение подходящего <math>a</math> — менее сложная задача. Согласно Нилу Коблицу, значение <math> a = 2</math> часто подходит для проверки критерием Поклингтона.
Оценка вычислительной сложности
Хотя тест Поклингтона и позволяет доказать лишь то, что число <math>n</math> является простым при верно выбранном <math>a</math>, можно оценить его алгоритмическую сложность в предположении, что мы выбрали его верно. Вычислительная сложность теста будет складываться из сложности факторизации числа <math>n</math> и числа <math>a^{(n-1)/q} -1 </math>. При использовании алгоритмов факторизации с субэкспоненциальной сложностью её можно ограничить сверху величиной <math>L_{a^n}[\alpha,c]</math> обозначенной в L-нотации, где <math>\alpha</math> и <math>c</math> зависят от выбора алгоритма факторизации.
Пример
Докажем, что число <math> n=31</math> является простым. Найдём простой делитель числа <math> n-1</math>, то есть 30. Им является <math> q=5</math>, причём <math>5 > \sqrt {31} -1</math>. Число a=2 удовлетворяет обоим критериям:
- <math>2^{30} \equiv 1 \pmod {31}</math>
- числа <math> 31</math> и <math>2^{(31-1)/5} -1 </math> взаимнопросты,
Следовательно число 31 простое по критерию Поклингтона
Частные случаи
Частным случаем критерия Поклингтона является теорема Прота, являющаяся тестом простоты для чисел Прота <math>n=2^{k}R+1</math>, где <math>R</math> — нечётно и<math>R<2^{k}</math>. Она имеет следующий вид:
Пусть <math>n=2^{k}R+1</math>, где <math>R<2^k</math>, <math> Z < 2^k + 1</math>, и <math>Z</math> не делит <math>R</math>. Тогда <math>n</math> — простое число в том и только в том случае, если выполняется условие <math> Z^{(n - 1)/2} = -1 \pmod{n}</math>.
См. также
Литература
- Н. Коблиц, Курс теории чисел и криптографии ISBN 5-94057-103-4
- Ю. В. Романец, П. А. Тимофеев, В. Ф. Шаньгин, Защита информации в компьютерных системах и сетях. 2-е изд, ISBN 5-256-01518-4
- А. В. Черемушкин, Лекции по арифметическим алгоритмам в криптографии ISBN 5-94057-060-7
