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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

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

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

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

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

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

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

то [math]\displaystyle{ n }[/math] — простое число.

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

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

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

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

Также стоит отметить, что этот критерий является вероятностым только в том смысле, что случайно выбранное число [math]\displaystyle{ a }[/math] может либо удовлетворять условию НОД [math]\displaystyle{ (a^{(n-1)/q} -1, n) = 1 }[/math], либо не удовлетворять ему. Если [math]\displaystyle{ n=RF+1 }[/math] — нечетное простое число, [math]\displaystyle{ F \gt \sqrt{n} - 1 }[/math], [math]\displaystyle{ F = q_1^{\alpha_1}q_2^{\alpha_2}...q_k^{\alpha_k}, }[/math] НОД [math]\displaystyle{ (R, F)=1 }[/math] то для случайно выбранного числа [math]\displaystyle{ 1 \lt a \lt n }[/math] эта вероятность есть [math]\displaystyle{ \prod_{i=1}^k(1-\frac{1}{q_i}) }[/math]. Однако, как только найдено такое [math]\displaystyle{ a }[/math], критерий доказывает, что [math]\displaystyle{ n }[/math] — простое число. В отличие от вероятностных тестов (таких, например, как тест Миллера-Рабина, тест Соловея-Штрассена и др.) заключение теста Поклингтона — вполне определённое.

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

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

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

Пример

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

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

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

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

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

Пусть [math]\displaystyle{ n=2^{k}R+1 }[/math], где [math]\displaystyle{ R\lt 2^k }[/math], [math]\displaystyle{ Z \lt 2^k + 1 }[/math], и [math]\displaystyle{ Z }[/math] не делит [math]\displaystyle{ R }[/math]. Тогда [math]\displaystyle{ n }[/math] — простое число в том и только в том случае, если выполняется условие [math]\displaystyle{ Z^{(n - 1)/2} = -1 \pmod{n} }[/math].

См. также

Литература

  1. Н. Коблиц, Курс теории чисел и криптографии ISBN 5-94057-103-4
  2. Ю. В. Романец, П. А. Тимофеев, В. Ф. Шаньгин, Защита информации в компьютерных системах и сетях. 2-е изд, ISBN 5-256-01518-4
  3. А. В. Черемушкин, Лекции по арифметическим алгоритмам в криптографии ISBN 5-94057-060-7
Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Критерий_Поклингтона&oldid=12358915