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

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

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

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

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

то ${\displaystyle n}$ просте.

Якщо такого числа a не існує, то ${\displaystyle 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.

Якщо ${\displaystyle 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}}.}$

Якщо ${\displaystyle n}$ — складене, то або ${\displaystyle (a,n)>1}$ і тоді ${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$, або ${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$. Якщо припустити, що для цього ${\displaystyle 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.

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

Наприклад, візьмемо ${\displaystyle 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 просте.

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

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

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

Введення: n > 2 - непарне число, що перевіряється на простоту; k - параметр, що визначає точність тесту
Вивід: просте, якщо n просте, в іншому випадку складене або можливо складене;
Визначаємо всі прості дільники ${\displaystyle n-1}$.
Цикл1: повторити k разів:                                          Вибираємо випадково 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 с