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

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

Для багатьох застосувань, як-от криптографія, ми потребуємо великих випадкових простих чисел. На щастя, великі прості не такі вже й рідкісні, тому можливо перевіряти цілі потрібного розміру, щоб знайти серед них просте. Функція розподілу простих чисел ${\displaystyle \pi (n)}$ визначає кількість простих чисел, які менші ніж ${\displaystyle n}$. Наприклад, ${\displaystyle \pi (10)=4.}$ Відомо, що

${\displaystyle \lim _{n\to \infty }{\frac {\pi (n)}{n/\lg n}}=1.}$

Це досить якісне наближена оцінка для ${\displaystyle \pi (n).}$ З цього ми маємо, що ймовірність того, що ${\displaystyle n}$ є простим дорівнює ${\displaystyle 1/\lg n}$. Геометричний розподіл підказує нам, що очікувана кількість спроб для знаходження простого числа становить ${\displaystyle \lg n}$. Також ми, звісно, можемо опустити парні числа, що зменшує кількість спроб удвічі.

Наївним способом перевірки чи число просте був би повний перебір можливих дільників. Тобто для числа ${\displaystyle n}$ потрібно було б перебрати ${\displaystyle 2,3,\dots ,\lfloor {\sqrt {n}}\rfloor }$. Знов-таки, ми можемо пропускати парні числа більші ніж двійка. Якщо вважати, що кожне пробне ділення потребує однаково часу, то складність буде ${\displaystyle O({\sqrt {n}})}$, така складність є експоненційною для ${\displaystyle n}$. Алгоритми з такою складністю, зазвичай вважають повільними. Хоча у такого алгоритму є й перевага, він знаходить дільники ${\displaystyle n}$, тобто розкладає число.

Найвідомішими ймовірнісними тестами простоти є тест Соловея — Штрассена і тест Міллера — Рабіна. В обох випадках базова процедура та сама: ми визначаємо множину ${\displaystyle W}$ свідків того, що ${\displaystyle n}$ є складеним. Якщо ми можемо знайти ${\displaystyle w\in W,}$ тоді ${\displaystyle W\neq \emptyset ,}$ і ${\displaystyle n}$ є складеним числом. У випадку тесту Міллера — Рабіна ${\displaystyle W:={\overline {W_{n}}}.}$

Нехай ${\displaystyle n\in \mathbb {N} }$ буде непарним числом і нехай ${\displaystyle n-1=2^{t}m,}$ з непарним ${\displaystyle m.}$ Припустимо, що ${\displaystyle n}$ просте. Тоді квадратними коренями з ${\displaystyle 1}$ будуть лише ${\displaystyle \pm 1,}$ тобто єдиними розв'язками ${\displaystyle x^{2}-1}$ за модулем 2. Більше того, ${\displaystyle a^{n-1}\equiv 1\mod n}$ для кожного ${\displaystyle a\in \mathbb {N} ,}$ яке просте з ${\displaystyle n.}$ Отже,

${\displaystyle a^{n-1}\equiv 1\mod n}$ і ${\displaystyle a^{(n-1)/2}\equiv \pm 1\mod n,}$ і

якщо ${\displaystyle a^{(n-1)/2}\equiv 1\mod n,}$ тоді ${\displaystyle a^{(n-1)/4}\equiv \pm 1\mod n,}$ і

якщо ${\displaystyle a^{(n-1)/4}\equiv 1\mod n,}$ тоді ${\displaystyle \dots }$

Ми бачимо: якщо ${\displaystyle n}$ є простим, тоді для кожного ${\displaystyle a\in \mathbb {N} }$ за умови, що ${\displaystyle \gcd(a,n)=1,}$ або ${\displaystyle a^{m}\equiv 1\mod n,}$ або існує ${\displaystyle j\in \{0,\dots ,t-1\}}$ з ${\displaystyle a^{2^{j}m}\equiv -1\mod n.}$ Зворотнє твердження також істинне, тобто, якщо ${\displaystyle n}$ є складеним, тоді існує ${\displaystyle a\in \mathbb {N} }$ з ${\displaystyle \gcd(a,n)=1,}$ таке що ${\displaystyle a^{m}\not \equiv 1\mod n}$ і ${\displaystyle a^{2^{j}m}\not \equiv -1\mod n}$ для ${\displaystyle 0\leq j\leq t-1.}$ І точніше:

Теорема: Нехай ${\displaystyle n\in \mathbb {N} }$ буде складеним непарним числом. Нехай ${\displaystyle n-1=2^{t}m,}$ з непарним ${\displaystyle m.}$ Нехай

${\displaystyle {\overline {W_{n}}}=\{[a]\in \mathbb {Z} _{n}^{*}|a^{m}\not \equiv 1\mod n,a^{2^{j}m}\not \equiv -1\mod n,0\leq j\leq t-1\}.}$

Тоді ${\displaystyle |{\overline {W}}_{n}|\geq \varphi {(n)}/2.}$

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

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

Імовірність помилки ${\displaystyle \leq 1/4^{k}.}$

• Тест Соловея — Штрассена

• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 31 Теоретико-числові алгоритми. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
• Hans Delfs; Helmut Knebl. A.8 Primes and Primality Tests. Introduction to Cryptography. Principles and Applications (вид. 2). Springer. с. 319—324. ISBN 978-3-540-49243-6.