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

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

Опис

Нехай $n>1$ — натуральне число. Якщо існує ціле $a$ таке, що $1<a<n$ і

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

і для довільного простого дільника $q$ числа $n-1$

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

то $n$ просте.

Якщо такого числа a не існує, то $n$ — складене число.

Правильність цього твердження полягає в наступному: якщо перша еквівалентність виконується для a, то можна зробити висновок про те, що a та n є спільними. Якщо a також зберігається другий крок, то порядок a у групі (Z/nZ)* дорівнює n−1, що означає, що порядок цієї групи n−1 (оскільки порядок кожного елемента групи ділить порядок групи), маючи на увазі, що n є простим. І навпаки, якщо n є простим, то існує первісний корінь модуля n або генератор групи (Z/nZ)*. Такий генератор має порядок |(Z/nZ)*| = n−1 , і обидва еквівалентності будуть виконуватися для будь-якого такого первісного кореня.

Зверніть увагу, що якщо існує a < n така, що перша еквівалентність не виконується, a називається свідком складності Ферма від n.

Доведення

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

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

Якщо $n$ — складене, то або $(a,n)>1$ і тоді $a^{n-1}\not \equiv 1{\pmod {n}}$, або $a^{n-1}\equiv 1{\pmod {n}}$. Якщо припустити, що для цього $a$ ще й виконується $a^{\frac {n-1}{q}}\not \equiv 1{\pmod {n}}$, то, оскільки ${\frac {n-1}{q}}\mid n-1$, отримуємо, що група $\mathbb {Z} _{n}^{\times }$ має елемент порядку $n-1$, значить $|\mathbb {Z} _{n}^{\times }|$ ділить $n-1$, що суперечить тому, що $|\mathbb {Z} _{n}^{\times }|=\varphi (n)<n-1$ при складених n.

Згідно з законом контрапозиції отримуємо критерій Люка.

Приклад

Наприклад, візьмемо $n=71$. Тоді $n-1=70=2\cdot 5\cdot 7$. Виберемо випадково $a=17$. Рахуємо:

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

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

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

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

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

На жаль $17^{10}\equiv 1\equiv 1{\pmod {71}}.$ Тому ми поки не можемо стверджувати, що 71 просте.

Спробуємо інше випадкове число a, виберемо $a=11$. Рахуємо:

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

Знову перевіримо порівняння $a^{\frac {n-1}{q}}\not \equiv 1{\pmod {n}}$ для $q=2;5;7~$:

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

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

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

Таким чином, 71 просте.

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

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

Алгоритм

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

Введення: n > 2 - непарне число, що перевіряється на простоту; k - параметр, що визначає точність тесту
Вивід: просте, якщо n просте, в іншому випадку складене або можливо складене;
Визначаємо всі прості дільники $n-1$.
Цикл1: повторити k разів:                                          Вибираємо випадково a із інтервалу [2, n − 1]
      Якщо $a^{n-1}\not \equiv 1{\pmod {n}}$ повернути складене
      Інакше 
         Цикл2: Для всіх простих $q\mid n-1$:
            Якщо $a^{\frac {n-1}{q}}\not \equiv 1{\pmod {n}}$
               Якщо ми не перевірили порівняння для всіх $q$
                  то продовжуємо виконувати Цикл2
               інакше повернути просте
            Інакше повертаємося до Циклу1
Повернути можливо складене.

Див. також

• Мала теорема Ферма
• Тест простоти

Література

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