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

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

Описание

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

$a^{n-1}\equiv 1(\mathrm{mod}n)$

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

$a^{\frac{n-1}{q}}\equiv ̸1(\mathrm{mod}n)$

то n простое.

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

Доказательство

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

$a^{\frac{n-1}{q}}\equiv ̸1(\mathrm{mod}n).$

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

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

Пример

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

$17^{70}\equiv 1(\mathrm{mod}71).$

Проверим сравнения $a^{\frac{n-1}{q}}\equiv ̸1(\mathrm{mod}n)$ для $q=2;5;7$:

$17^{35}\equiv 70\equiv ̸1(\mathrm{mod}71)$

$17^{14}\equiv 25\equiv ̸1(\mathrm{mod}71)$

$17^{10}\equiv 1\equiv 1(\mathrm{mod}71).$

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

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

$11^{70}\equiv 1(\mathrm{mod}71).$

Снова проверим сравнения $a^{\frac{n-1}{q}}\equiv ̸1(\mathrm{mod}n)$ для $q=2;5;7$:

$11^{35}\equiv 70\equiv ̸1(\mathrm{mod}71)$

$11^{14}\equiv 54\equiv ̸1(\mathrm{mod}71)$

$11^{10}\equiv 32\equiv ̸1(\mathrm{mod}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}\equiv ̸1(\mathrm{mod}n)$ вернуть составное
      Иначе 
         Цикл2: Для всех простых $q\mid n-1$:
            Если $a^{\frac{n-1}{q}}\equiv ̸1(\mathrm{mod}n)$
               Если мы не проверили сравнение для всех $q$
                  то продолжаем выполнять Цикл2
               иначе вернуть простое
            Иначе возвращаемся к Циклу1
Вернуть возможно составное.

См. также

• Тест простоты

Литература

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии, МЦНМО, 2003
• Трост Э. — Primzahlen / Простые числа — М.: ГИФМЛ, 1959, 135 с