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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

і для довільного простого дільника числа

то просте.

Якщо такого числа 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
Повернути можливо складене.

Примітки

[ред. | ред. код]
  1. Crandall, Richard; Pomerance, Carl (2005). Prime Numbers: a Computational Perspective (2nd edition). Springer. с. 173. ISBN 0-387-25282-7.
  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 0-387-95332-9.

Див. також

[ред. | ред. код]

Література

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