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

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

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

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

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

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

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

Тоді

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

Псевдокод МІЛЛЕР-РАБІН якщо парне тоді  повернути ХИБА

поки парне

для до

 якщо тоді

   поки і

   якщо тоді     повернути ХИБА повернути ІСТИНА Імовірність помилки

Див. також Тест Соловея — Штрассена

Примітки

Джерела