В теорії чисел тест простоти Люка — це тест простоти натурального числа n; для його роботи необхідно знати розкладання на прості множники. Вони утворюють базис для , який дозволяє підтвердити за поліноміальний час, що число є простим.
Опис Нехай — натуральне число. Якщо існує ціле таке, що і
і для довільного простого дільника числа
то просте.
Якщо такого числа a не існує, то — складене число.
Правильність цього твердження полягає в наступному: якщо перша еквівалентність виконується для 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.
Згідно з законом контрапозиції отримуємо критерій Люка.
Приклад Наприклад, візьмемо . Тоді . Виберемо випадково . Рахуємо:
Перевіримо порівняння для :
На жаль Тому ми поки не можемо стверджувати, що 71 просте.
Спробуємо інше випадкове число a, виберемо . Рахуємо:
Знову перевіримо порівняння для :
Таким чином, 71 просте.
Зауважимо, що для швидкого обчислення ступенів по модулю використовується алгоритм двійкового зведення в ступінь із взяттям залишку по модулю після кожного множення.
Зауважимо також, що при простому з узагальненої гіпотези Рімана випливає, що серед перших чисел є хоча б одне, що створює групу ,т ому умовно можна стверджувати, що підібрати основу можна за поліноміальний час.
Алгоритм
Алгоритм, написаний псевдокодом, такий:
Введення: n > 2 - непарне число, що перевіряється на простоту; k - параметр, що визначає точність тесту Вивід: просте, якщо n просте, в іншому випадку складене або можливо складене; Визначаємо всі прості дільники . Цикл1: повторити k разів: Вибираємо випадково a із інтервалу [2, n − 1] Якщо повернути складене Інакше Цикл2: Для всіх простих : Якщо Якщо ми не перевірили порівняння для всіх то продовжуємо виконувати Цикл2 інакше повернути просте Інакше повертаємося до Циклу1 Повернути можливо складене.
Примітки
Див. також Мала теорема Ферма Тест простоти
Література Василенко О. Н. Теоретико-числовые алгоритмы в криптографии, МЦНМО, 2003 Трост Э. — Primzahlen / Простые числа — М.: ГИФМЛ, 1959, 135 с