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

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

Вступ

Для багатьох застосувань, як-от криптографія, ми потребуємо великих випадкових простих чисел. На щастя, великі прості не такі вже й рідкісні, тому можливо перевіряти цілі потрібного розміру, щоб знайти серед них просте. Функція розподілу простих чисел ${\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 (n,k)}$ якщо ${\displaystyle n}$ парне тоді  повернути ХИБА ${\displaystyle m\gets (n-1)\ {\mbox{div}}\ 2;t\gets 1}$ поки ${\displaystyle m}$ парне  ${\displaystyle m\gets m\ {\mbox{div}}\ 2;t\gets t+1}$ для ${\displaystyle i\gets 1}$ до ${\displaystyle k}$  ${\displaystyle a\gets Random()\mod n}$  ${\displaystyle u\gets a^{m}\mod n}$  якщо ${\displaystyle u\neq 1}$ тоді   ${\displaystyle j\gets 1}$    поки ${\displaystyle u\neq n-1}$ і ${\displaystyle j<t}$     ${\displaystyle u\gets u^{2}\mod n;j\gets j+1}$    якщо ${\displaystyle u\neq n-1}$ тоді     повернути ХИБА повернути ІСТИНА

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

Див. також

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

Примітки

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

Джерела

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