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

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

Описание


 Пусть n \textgreater 1 — натуральное число. Если существует целое a такое, что $1
an11(modn)

 и для любого простого делителя q числа n1
an1q1(modn)

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

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


 Если n простое, то группа вычетов Zn циклична, то есть имеет образующую g, порядок которой совпадает с порядком группы |Zn×|=n1, а значит, для любого простого делителя q числа n1 выполняется сравнение:

an1q1(modn).
  Если n — составное, то либо НОД(a,n)>1 и тогда an11(modn), либо an11(modn). Если предположить, что для этого a ещё и выполняется an1q1(modn), то, поскольку n1qn1, получаем, что группа Zn× имеет элемент порядка n1, значит |Zn×| делит n1, что противоречит тому, что $|\mathbb{Z}_n^{\times}| =\varphi (n)n.
 По закону контрапозиции получаем критерий Люка.

Пример


 Например, возьмем n = 71. Тогда n1=70=257. Выберем случайно a=17. Вычисляем:
17701(mod71).

 Проверим сравнения an1q1(modn) для q=2;5;7:
1735701(mod71)

1714251(mod71)

171011(mod71).

 К сожалению 171011(mod71).. Поэтому мы пока не можем утверждать, что 71 простое.
 Попробуем другое случайное число a, выберем a=11. Вычисляем:
11701(mod71).

 Снова проверим сравнения an1q1(modn) для q=2;5;7:
1135701(mod71)

1114541(mod71)

1110321(mod71).

 Таким образом, 71 простое.
 Заметим, что для быстрого вычисления степеней по модулю используется алгоритм двоичного возведения в степень со взятием остатка по модулю n после каждого умножения.
 Заметим также, что при простом n из обобщенной гипотезы Римана вытекает, что среди первых O(ln2n) чисел есть хотя бы одна образующая группы Zn, поэтому условно можно утверждать, что подобрать основание a можно за полиномиальное время.

Алгоритм


 Алгоритм, написанный псевдокодом, следующий:
\textttВвод\texttt: \textttn\texttt \textgreater 2 - нечетное число, тестируемое на простоту; \textttk\texttt - параметр, определяющий точность теста\\\textttВывод\texttt: \textttпростое\texttt, если \textttn\texttt простое, в противном случае \textttсоставное\texttt либо \textttвозможно \textttсоставное\texttt;\\\textttОпределяем все простые делители n1\texttt.\\\textttЦикл1: Выбираем случайно \texttta\texttt из интервала [2, \textttn\texttt − 1]\\\texttt      Если an11(modn)\texttt вернуть \textttсоставное\\\texttt      Иначе \\\texttt         Цикл2: Для всех простых qn1\texttt:\\\texttt            Если an1q1(modn)\\\texttt               Если мы не проверили сравнение для всех q\\\texttt                  то продолжаем выполнять Цикл2\\\texttt               иначе вернуть \textttпростое\\\texttt            Иначе возвращаемся к Циклу1\\\textttВернуть \textttвозможно \textttсоставное\texttt.