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

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

Пусть   где q — простое число,  . Если существует такое целое число  , что   и НОД , то каждый простой делитель   числа   имеет вид   при некотором натуральном  .

Доказательство править

Пусть   — простой делитель числа  . Тогда из условия теоремы вытекает, что   и  . Отсюда получаем, что порядок   элемента   по модулю   удовлетворяет условиям: , где   — некоторое целое. Допустим,   делит  . В этом случае  , где   — целое. Следовательно  , что невозможно. Поскольку  , то   делится на  . Однако   должно делить число   Следовательно,  при некотором  . Теорема доказана.

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

Пусть   — натуральное число. Пусть число   имеет простой делитель  , причем  . Если найдётся такое целое число  , что выполняются следующие два условия:

  1.  
  2. числа   и   взаимнопросты,

то   — простое число.

Доказательство править

Предположим, что   является составным числом. Тогда существует простое число   — делитель  , причем  . Заметим, что  , следовательно   и   — взаимнопросты. Следовательно, существует некоторое целое число  , такое, что  . Но в таком случае   (в силу условия 1)). Но таким образом получено противоречие условию 2). Следовательно,   является простым числом.

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

В отличие от теоремы Сэлфриджа, критерий Поклингтона не требует знания полного разложения числа   на простые сомножители и позволяет ограничиться частичной факторизацией числа  . Он подходит для проверки на простоту при условии, что   делится на простое число  , а также если   можно найти и доказать его простоту.

Также стоит отметить, что этот критерий является вероятностым только в том смысле, что случайно выбранное число   может либо удовлетворять условию НОД  , либо не удовлетворять ему. Если   — нечетное простое число,  ,   НОД   то для случайно выбранного числа   эта вероятность есть  . Однако, как только найдено такое  , критерий доказывает, что   — простое число. В отличие от вероятностных тестов (таких, например, как тест Миллера-Рабина, тест Соловея-Штрассена и др.) заключение теста Поклингтона — вполне определённое.

Наибольшей трудностью связанной с использованием данного критерия может являться необходимость нахождения простого делителя числа  , что может свестись на практике к полной факторизации. Нахождение подходящего   — менее сложная задача. Согласно Нилу Коблицу, значение   часто подходит для проверки критерием Поклингтона.

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

Хотя тест Поклингтона и позволяет доказать лишь то, что число   является простым при верно выбранном  , можно оценить его алгоритмическую сложность в предположении, что мы выбрали его верно. Вычислительная сложность теста будет складываться из сложности факторизации числа   и числа  . При использовании алгоритмов факторизации с субэкспоненциальной сложностью её можно ограничить сверху величиной   обозначенной в L-нотации, где   и   зависят от выбора алгоритма факторизации.

Пример править

Докажем, что число   является простым. Найдём простой делитель числа  , то есть 30. Им является  , причём  . Число a=2 удовлетворяет обоим критериям:

  1.  
  2. числа   и   взаимнопросты,

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

Частные случаи править

Частным случаем критерия Поклингтона является теорема Прота, являющаяся тестом простоты для чисел Прота  , где   — нечётно и . Она имеет следующий вид:

Пусть  , где  ,  , и   не делит  . Тогда   — простое число в том и только в том случае, если выполняется условие  .

См. также править

Литература править

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