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

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

Тест простоти Міллера–Рабіна або тест Міллера–Рабіна — це тест простоти: алгоритм, який визначає чи є надане число простим. Його початкова версія, яку розробив професор Міллер, є детерміністичною, але детермінізм покладається на недоведену узагальнену гіпотезу Рімана;[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. 

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