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

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

Опис

Нехай ${\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 Повернути можливо складене. 

Примітки

1. Crandall, Richard; Pomerance, Carl (2005). Prime Numbers: a Computational Perspective (2nd edition). Springer. с. 173. ISBN .
2. Křížek, Michal; Luca, Florian; Somer, Lawrence (2001). 17 Lectures on Fermat Numbers: From Number Theory to Geometry. CMS Books in Mathematics. Т. 9. Canadian Mathematical Society/Springer. с. 41. ISBN .

Див. також

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

Література

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