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

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

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

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

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

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

то n простое.

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

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

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

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

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

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

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

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

${\displaystyle 17^{35}\equiv 70\not \equiv 1{\pmod {71}}}$

${\displaystyle 17^{14}\equiv 25\not \equiv 1{\pmod {71}}}$

${\displaystyle 17^{10}\equiv 1\equiv 1{\pmod {71}}.}$

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

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

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

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

${\displaystyle 11^{35}\equiv 70\not \equiv 1{\pmod {71}}}$

${\displaystyle 11^{14}\equiv 54\not \equiv 1{\pmod {71}}}$

${\displaystyle 11^{10}\equiv 32\not \equiv 1{\pmod {71}}.}$

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

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

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

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

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

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

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