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

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

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

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

Пусть 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 числа a имеет вид p = q^kr + 1 при некотором натуральном r

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

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

  1. a^{n-1} \equiv 1 \pmod n
  2. числа 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 делится на простое число q > \sqrt {n} -1 , а также если q можно найти и доказать его простоту. Иначе, этим критерием пользоваться нельзя. Так же стоит отметить, что этот критерий является вероятностым только в том смысле, что случайно выбранное число a может либо удовлетворять условию НОД ~(a^{(n-1)/q} -1, n) = 1 , либо не удовлетворять ему. Однако, как только найдено такое a, критерий доказывает, что n - простое число. В отличие от вероятностных тестов (таких, например, как тест Миллера-Рабина, тест Соловея-Штрассена и др.) заключение теста Поклингтона - вполне определенное.

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

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

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