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

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

Вступ

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

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

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

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

Ймовірнісні тести простоти

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

Оцінка кількості свідків

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

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

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

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

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

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

${\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\}.$

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

Порівняння з тестом Соловея—Штрассена

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

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

Псевдокод

МІЛЛЕР-РАБІН$(n,k)$ якщо $n$ парне тоді  повернути ХИБА $m\gets (n-1)\ {\mbox{div}}\ 2;t\gets 1$ поки $m$ парне  $m\gets m\ {\mbox{div}}\ 2;t\gets t+1$ для $i\gets 1$ до $k$  $a\gets Random()\mod n$  $u\gets a^{m}\mod n$  якщо $u\neq 1$ тоді   $j\gets 1$    поки $u\neq n-1$ і $j<t$     $u\gets u^{2}\mod n;j\gets j+1$    якщо $u\neq n-1$ тоді     повернути ХИБА повернути ІСТИНА

Імовірність помилки $\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.