Тест простоти Міллера–Рабіна

Тест простоти Міллера — Рабіна або тест Міллера – Рабіна — це тест простоти: алгоритм, який визначає чи є надане число простим. Його початкова версія, яку розробив професор Міллер, є детерміністичною, але детермінізм покладається на недоведену узагальнену гіпотезу Рімана;[1] Міхаель Рабін змінив її, щоб отримати безумовний імовірнісний алгоритм.[2]

ВступРедагувати

Для багатьох застосувань, як-от криптографія, ми потребуємо великих випадкових простих чисел. На щастя, великі прості не такі вже й рідкісні, тому можливо перевіряти цілі потрібного розміру, щоб знайти серед них просте. Функція розподілу простих чисел   визначає кількість простих чисел, які менші ніж  . Наприклад,   Відомо, що

 

Це досить якісне наближена оцінка для   З цього ми маємо, що ймовірність того, що   є простим дорівнює  . Геометричний розподіл підказує нам, що очікувана кількість спроб для знаходження простого числа становить  . Також ми, звісно, можемо опустити парні числа, що зменшує кількість спроб удвічі.

Наївним способом перевірки чи число просте був би повний перебір можливих дільників. Тобто для числа   потрібно було б перебрати  . Знов-таки, ми можемо пропускати парні числа більші ніж двійка. Якщо вважати, що кожне пробне ділення потребує однаково часу, то складність буде  , така складність є експоненційною для  . Алгоритми з такою складністю, зазвичай вважають повільними. Хоча у такого алгоритму є й перевага, він знаходить дільники  , тобто розкладає число.

Ймовірнісні тести простотиРедагувати

Найвідомішими ймовірнісними тестами простоти є тест Соловея — Штрассена і тест Міллера — Рабіна. В обох випадках базова процедура та сама: ми визначаємо множину   свідків того, що   є складеним. Якщо ми можемо знайти   тоді   і   є складеним числом. У випадку тесту Міллера — Рабіна  

Оцінка кількості свідківРедагувати

Нехай   буде непарним числом і нехай   з непарним   Припустимо, що   просте. Тоді квадратними коренями з   будуть лише   тобто єдиними розв'язками   за модулем 2. Більше того,   для кожного   яке просте з   Отже,

  і   і
якщо   тоді   і
якщо   тоді  

Ми бачимо: якщо   є простим, тоді для кожного   за умови, що   або   або існує   з   Зворотнє твердження також істинне, тобто, якщо   є складеним, тоді існує   з   таке що   і   для   І точніше:

Теорема: Нехай   буде складеним непарним числом. Нехай   з непарним   Нехай

 

Тоді  

Порівняння з тестом Соловея—ШтрассенаРедагувати

Тест Міллера — Рабіна буде кращим вибором:

  1. Легше обчислити тестові умови.
  2. Свідок для тесту Соловея—Штрассена також свідок для тесту Міллера — Рабіна.
  3. У тесті Міллера — Рабіна ймовірність натрапити на свідка за одну випадкову спробу більша ніж 3/4, а у тесті Соловея—Штрассена 1/2.

ПсевдокодРедагувати

МІЛЛЕР-РАБІН 

  1. якщо   парне тоді
  2. повернути ХИБА
  3.  
  4. поки   парне
  5.  
  6. для   до  
  7.  
  8.  
  9. якщо   тоді
  10.    
  11.    поки   і  
  12.      
  13.    якщо   тоді
  14.     повернути ХИБА
  15. повернути ІСТИНА

Імовірність помилки  

Див. такожРедагувати

ПриміткиРедагувати

  1. Гарі Міллер (1976). Ріманова гіпотеза і тест на простоту. Journal of Computer and System Sciences 13 (3): 300–317. doi:10.1145/800116.803773. 
  2. Міхаель Рабін (1980). Ймовірнісний алгоритм для перевірки простоти. Journal of Number Theory 12 (1): 128–138. doi:10.1016/0022-314X(80)90084-0. 

ДжерелаРедагувати