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

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

В теории чисел тест простоты Люка — это тест простоты натурального числа n; для его работы необходимо знать разложение n-1 на множители. Для простого числа n простые множители числа n-1 вместе с некоторым основанием a составляют сертификат Пратта, который позволяет подтвердить за полиномиальное время, что число n является простым.

Описание[править | править исходный текст]

Пусть n > 1 — натуральное число. Если существует целое a такое, что 1<a<n и

a^{n-1} \equiv 1 \pmod n

и для любого простого делителя q числа n-1

a^{\frac{n-1}{q}} \not\equiv 1 \pmod n

то n простое.

Если такого числа a не существует, то nсоставное число.

Доказательство[править | править исходный текст]

Если n простое, то группа вычетов \mathbb{Z}_n циклична, то есть имеет образующую g, порядок которой совпадает с порядком группы |\mathbb{Z}_n^{\times}|=n-1, а значит, для любого простого делителя q числа n-1 выполняется сравнение:

a^{\frac{n-1}{q}} \not\equiv 1 \pmod n.

Если n — составное, то либо \text{НОД}(a,n)>1 и тогда a^{n-1} \not\equiv 1 \pmod n, либо a^{n-1} \equiv 1 \pmod n. Если предположить, что для этого a ещё и выполняется a^{\frac{n-1}{q}} \not\equiv 1 \pmod n, то, поскольку \frac{n-1}{q} \mid n-1, получаем, что группа \mathbb{Z}_n^{\times} имеет элемент порядка n-1, значит |\mathbb{Z}_n^{\times}| делит n-1, что противоречит тому, что |\mathbb{Z}_n^{\times}| =\varphi (n)<n-1 при составных n.

По закону контрапозиции получаем критерий Люка.

Пример[править | править исходный текст]

Например, возьмем n = 71. Тогда n-1=70 = 2 \cdot 5 \cdot 7. Выберем случайно a=17. Вычисляем:

17^{70} \equiv 1 \pmod {71}.

Проверим сравнения a^{\frac{n-1}{q}} \not\equiv 1 \pmod n для q=2;5;7~:

17^{35} \equiv 70 \not\equiv 1 \pmod {71}
17^{14} \equiv 25 \not\equiv 1 \pmod {71}
17^{10} \equiv 1 \equiv 1 \pmod {71}.

К сожалению 17^{10} \equiv 1 \equiv 1 \pmod {71}.. Поэтому мы пока не можем утверждать, что 71 простое.

Попробуем другое случайное число a, выберем a=11. Вычисляем:

11^{70} \equiv 1 \pmod {71}.

Снова проверим сравнения a^{\frac{n-1}{q}} \not\equiv 1 \pmod n для q=2;5;7~:

11^{35} \equiv 70 \not\equiv 1 \pmod {71}
11^{14} \equiv 54 \not\equiv 1 \pmod {71}
11^{10} \equiv 32 \not\equiv 1 \pmod {71}.

Таким образом, 71 простое.

Заметим, что для быстрого вычисления степеней по модулю используется алгоритм двоичного возведения в степень со взятием остатка по модулю n после каждого умножения.

Заметим также, что при простом n из обобщенной гипотезы Римана вытекает, что среди первых O(\ln ^2 n)~ чисел есть хотя бы одна образующая группы \mathbb{Z}_n, поэтому условно можно утверждать, что подобрать основание a можно за полиномиальное время.

Алгоритм[править | править исходный текст]

Алгоритм, написанный псевдокодом, следующий:

Ввод: n > 2 - нечетное число, тестируемое на простоту; k - параметр, определяющий точность теста
Вывод: простое, если n простое, в противном случае составное либо возможно составное;
Определяем все простые делители n-1.
Цикл1: Выбираем случайно a из интервала [2, n − 1]
      Если a^{n-1} \not\equiv 1 \pmod n вернуть составное
      Иначе 
         Цикл2: Для всех простых q \mid n-1:
            Если a^{\frac{n-1}{q}} \not\equiv 1 \pmod n
               Если мы не проверили сравнение для всех q
                  то продолжаем выполнять Цикл2
               иначе вернуть простое
            Иначе возвращаемся к Циклу1
Вернуть возможно составное.

См. также[править | править исходный текст]

Литература[править | править исходный текст]

  • Василенко О. Н. Теоретико-числовые алгоритмы в криптографии, МЦНМО, 2003
  • Трост Простые числа