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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Теорема Поклингтона[править | править вики-текст]

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

Доказательство теоремы Поклингтона[править | править вики-текст]

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

Критерий Поклингтона[править | править вики-текст]

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

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

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

Доказательство критерия Поклингтона[править | править вики-текст]

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

Замечания к критерию Поклингтона[править | править вики-текст]

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

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

Оценка вычислительной сложности теста Поклингтона[править | править вики-текст]

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

Пример[править | править вики-текст]

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

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

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

Частные случаи критерия Поклингтона[править | править вики-текст]

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

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

См также[править | править вики-текст]

Литература[править | править вики-текст]

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