Loading AI tools
Из Википедии, свободной энциклопедии
Критерий Поклингтона — детерминированный тест на простоту, разработанный Генри Поклингтоном[англ.] и Дерриком Генри Лехмером. Критерий Поклингтона позволяет определять, является ли данное число простым.
Пусть где q — простое число, . Если существует такое целое число , что и НОД, то каждый простой делитель числа имеет вид при некотором натуральном .
Пусть — простой делитель числа . Тогда из условия теоремы вытекает, что и . Отсюда получаем, что порядок элемента по модулю удовлетворяет условиям:, где — некоторое целое. Допустим, делит . В этом случае , где — целое. Следовательно , что невозможно. Поскольку , то делится на . Однако должно делить число Следовательно, при некотором . Теорема доказана.
Пусть — натуральное число. Пусть число имеет простой делитель , причем . Если найдётся такое целое число , что выполняются следующие два условия:
то — простое число.
Предположим, что является составным числом. Тогда существует простое число — делитель , причем . Заметим, что , следовательно и — взаимнопросты. Следовательно, существует некоторое целое число , такое, что . Но в таком случае (в силу условия 1)). Но таким образом получено противоречие условию 2). Следовательно, является простым числом.
В отличие от теоремы Сэлфриджа, критерий Поклингтона не требует знания полного разложения числа на простые сомножители и позволяет ограничиться частичной факторизацией числа . Он подходит для проверки на простоту при условии, что делится на простое число , а также если можно найти и доказать его простоту.
Также стоит отметить, что этот критерий является вероятностым только в том смысле, что случайно выбранное число может либо удовлетворять условию НОД , либо не удовлетворять ему. Если — нечетное простое число, , НОД то для случайно выбранного числа эта вероятность есть . Однако, как только найдено такое , критерий доказывает, что — простое число. В отличие от вероятностных тестов (таких, например, как тест Миллера-Рабина, тест Соловея-Штрассена и др.) заключение теста Поклингтона — вполне определённое.
Наибольшей трудностью связанной с использованием данного критерия может являться необходимость нахождения простого делителя числа , что может свестись на практике к полной факторизации. Нахождение подходящего — менее сложная задача. Согласно Нилу Коблицу, значение часто подходит для проверки критерием Поклингтона.
Хотя тест Поклингтона и позволяет доказать лишь то, что число является простым при верно выбранном , можно оценить его алгоритмическую сложность в предположении, что мы выбрали его верно. Вычислительная сложность теста будет складываться из сложности факторизации числа и числа . При использовании алгоритмов факторизации с субэкспоненциальной сложностью её можно ограничить сверху величиной обозначенной в L-нотации, где и зависят от выбора алгоритма факторизации.
Докажем, что число является простым. Найдём простой делитель числа , то есть 30. Им является , причём . Число a=2 удовлетворяет обоим критериям:
Следовательно число 31 простое по критерию Поклингтона
Частным случаем критерия Поклингтона является теорема Прота, являющаяся тестом простоты для чисел Прота , где — нечётно и. Она имеет следующий вид:
Пусть , где , , и не делит . Тогда — простое число в том и только в том случае, если выполняется условие .
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.