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

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

ОписаниеПравить

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

$a^{n-<!--\; -\; -->1}\equiv <!--\; \equiv \; -->1(\mathrm{mod}n)$$a^{n-1} \equiv 1 \pmod n$ 

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

$a^{\frac{n-<!--\; -\; -->1}{q}}\not\equiv 1(\mathrm{mod}n)$$a^{\frac {n-1}{q}}\not \equiv 1{\pmod {n}}$ 

то n простое.

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

ДоказательствоПравить

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

$a^{\frac{n-<!--\; -\; -->1}{q}}\not\equiv 1(\mathrm{mod}n).$$a^{\frac {n-1}{q}}\not \equiv 1{\pmod {n}}.$ 

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

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

ПримерПравить

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

${17}^{70}\equiv <!--\; \equiv \; -->1(\mathrm{mod}71).$$17^{70}\equiv 1{\pmod {71}}.$ 

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

${17}^{35}\equiv <!--\; \equiv \; -->70\not\equiv 1(\mathrm{mod}71)$$17^{35}\equiv 70\not \equiv 1{\pmod {71}}$ 

${17}^{14}\equiv <!--\; \equiv \; -->25\not\equiv 1(\mathrm{mod}71)$$17^{14}\equiv 25\not \equiv 1{\pmod {71}}$ 

${17}^{10}\equiv <!--\; \equiv \; -->1\equiv <!--\; \equiv \; -->1(\mathrm{mod}71).$$17^{10}\equiv 1\equiv 1{\pmod {71}}.$ 

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

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

${11}^{70}\equiv <!--\; \equiv \; -->1(\mathrm{mod}71).$$11^{70}\equiv 1{\pmod {71}}.$ 

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

${11}^{35}\equiv <!--\; \equiv \; -->70\not\equiv 1(\mathrm{mod}71)$$11^{35}\equiv 70\not \equiv 1{\pmod {71}}$ 

${11}^{14}\equiv <!--\; \equiv \; -->54\not\equiv 1(\mathrm{mod}71)$$11^{14}\equiv 54\not \equiv 1{\pmod {71}}$ 

${11}^{10}\equiv <!--\; \equiv \; -->32\not\equiv 1(\mathrm{mod}71).$$11^{10}\equiv 32\not \equiv 1{\pmod {71}}.$ 

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

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

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

АлгоритмПравить

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

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

См. такжеПравить

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

ЛитератураПравить

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