- Тест простоты Люка
-
В теории чисел тест простоты Люка — это тест простоты натурального числа n; для его работы необходимо знать разложение на множители. Для простого числа n простые множители числа вместе с некоторым основанием a составляют сертификат Пратта, который позволяет подтвердить за полиномиальное время, что число n является простым.
Содержание
Описание
Пусть n > 1 — натуральное число. Если существует целое a такое, что и
и для любого простого делителя q числа
то n простое.
Если такого числа a не существует, то n — составное число.
Доказательство
Если n простое, то группа вычетов циклична, то есть имеет образующую , порядок которой совпадает с порядком группы , а значит, для любого простого делителя числа выполняется сравнение:
Если n - составное, то либо и тогда , либо . Если предположить, что для этого a еще и выполняется , то, поскольку , мы получаем, что группа имеет элемент порядка , значит делит , что противоречит тому, что при составных n.
Теперь, по закону контрапозиции, получаем критерий Люка.
Пример
Например, возьмем n = 71. Тогда . Выберем случайно . Вычисляем:
Проверим сравнения для :
К сожалению . Поэтому мы пока не можем утверждать, что 71 простое.
Попробуем другое случайное число a, выберем . Вычисляем:
Снова проверим сравнения для :
Таким образом, 71 простое.
Заметим, что для быстрого вычисления степеней по модулю используется алгоритм двоичного возведения в степень со взятием остатка по модулю n после каждого умножения.
Заметим также, что при простом n из обобщенной гипотезы Римана вытекает, что среди первых чисел есть хотя бы одна образующая группы , поэтому условно можно утверждать, что подобрать основание a можно за полиномиальное время.
Алгоритм
Алгоритм, написанный псевдокодом следующий:
Ввод: n > 2 - нечетное число, тестируемое на простоту; k - параметр, определяющий точность теста Вывод: простое, если n простое, в противном случае составное либо возможно составное; Определяем все простые делители . Цикл1: Выбираем случайно a из интервала [2, n − 1] Если вернуть составное Иначе Цикл2: Для всех простых : Если Если мы не проверили сравнение для всех то продолжаем выполнять Цикл2 иначе вернуть простое Иначе возвращаемся к Циклу1 Вернуть возможно составное.
См. также
Литература
- Василенко О. Н. Теоретико-числовые алгоритмы в криптографии, МЦНМО, 2003
- Трост Простые числа
Теоретико-числовые алгоритмы Тесты простоты Поиск простых чисел Факторизация Перебор делителей • Метод Ферма • P-1 метод Полларда • Ρ-алгоритм Полларда • Метод Лемана • Метод эллиптических кривых (алгоритм Ленстры) • Алгоритм Диксона • Квадратичное решето
Дискретное логарифмирование Нахождение НОД Арифметика по модулю Умножение чисел Категории:- Теоретико-числовые алгоритмы
- Тесты простоты
Wikimedia Foundation. 2010.