Тест простоты Люка

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

В теории чисел тест простоты Люка — это тест простоты натурального числа 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
  • Трост Э. — Primzahlen / Простые числа — М.: ГИФМЛ, 1959, 135 с