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

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

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

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

1. $a^{n-1} \equiv 1 (mod ~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 (mod ~p-1)$. Но в таком случае $~a^{(n-1)/q}\equiv a^{uq(n-1)/q} = a^{u(n-1)} (mod ~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