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

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

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

Вступ[ред. | ред. код]

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

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

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

Ймовірнісні тести простоти[ред. | ред. код]

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

Оцінка кількості свідків[ред. | ред. код]

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

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

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

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

Тоді

Порівняння з тестом Соловея—Штрассена[ред. | ред. код]

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

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

Псевдокод[ред. | ред. код]

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

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

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

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  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. 

Джерела[ред. | ред. код]