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

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

Вступ

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

$\underset{n\to \mathrm{\infty }}{\lim }\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\ne \mathrm{\varnothing },$ і $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 1modn$ для кожного $a\in \mathbb{N},$ яке просте з $n.$ Отже,

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

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

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

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

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

$\overline{W_n}=\{[a]\in {\mathbb{Z}}_n^{*}|a^m\equiv ̸1modn,a^{2^{j}m}\equiv ̸-1modn,0\le j\le t-1\}.$

Тоді $|{\bar{W}}_n|\ge \phi (n)/2.$

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

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

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

Псевдокод

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

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

Див. також

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

Джерела

• Шаблон:CLRS
• Шаблон:Cite book