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

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

Описание

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

[math]\displaystyle{ a^{n-1} \equiv 1 \pmod n }[/math]

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

[math]\displaystyle{ a^{\frac{n-1}{q}} \not\equiv 1 \pmod n }[/math]

то n простое.

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

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

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

[math]\displaystyle{ a^{\frac{n-1}{q}} \not\equiv 1 \pmod n. }[/math]

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

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

Пример

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

[math]\displaystyle{ 17^{70} \equiv 1 \pmod {71}. }[/math]

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

[math]\displaystyle{ 17^{35} \equiv 70 \not\equiv 1 \pmod {71} }[/math]

[math]\displaystyle{ 17^{14} \equiv 25 \not\equiv 1 \pmod {71} }[/math]

[math]\displaystyle{ 17^{10} \equiv 1 \equiv 1 \pmod {71}. }[/math]

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

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

[math]\displaystyle{ 11^{70} \equiv 1 \pmod {71}. }[/math]

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

[math]\displaystyle{ 11^{35} \equiv 70 \not\equiv 1 \pmod {71} }[/math]

[math]\displaystyle{ 11^{14} \equiv 54 \not\equiv 1 \pmod {71} }[/math]

[math]\displaystyle{ 11^{10} \equiv 32 \not\equiv 1 \pmod {71}. }[/math]

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

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

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

Алгоритм

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

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

См. также

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

Литература

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