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

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

Опис

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

$a^{n-1}\equiv 1(\mathrm{mod}n)$

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

$a^{\frac{n-1}{q}}\equiv ̸1(\mathrm{mod}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}}\equiv ̸1(\mathrm{mod}n).$

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

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

Приклад

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

$17^{70}\equiv 1(\mathrm{mod}71).$

Перевіримо порівняння $a^{\frac{n-1}{q}}\equiv ̸1(\mathrm{mod}n)$ для $q=2;5;7$:

$17^{35}\equiv 70\equiv ̸1(\mathrm{mod}71)$

$17^{14}\equiv 25\equiv ̸1(\mathrm{mod}71)$

$17^{10}\equiv 1\equiv 1(\mathrm{mod}71).$

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

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

$11^{70}\equiv 1(\mathrm{mod}71).$

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

$11^{35}\equiv 70\equiv ̸1(\mathrm{mod}71)$

$11^{14}\equiv 54\equiv ̸1(\mathrm{mod}71)$

$11^{10}\equiv 32\equiv ̸1(\mathrm{mod}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}\equiv ̸1(\mathrm{mod}n)$ повернути складене
      Інакше 
         Цикл2: Для всіх простих $q\mid n-1$:
            Якщо $a^{\frac{n-1}{q}}\equiv ̸1(\mathrm{mod}n)$
               Якщо ми не перевірили порівняння для всіх $q$
                  то продовжуємо виконувати Цикл2
               інакше повернути просте
            Інакше повертаємося до Циклу1
Повернути можливо складене.

Див. також

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

Література

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