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

Материал из Википедии — свободной энциклопедии

Тест Миллера — Рабина — вероятностный полиномиальный тест простоты. Тест Миллера — Рабина позволяет эффективно определять, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа.

Содержание

1 Свидетели простоты и теорема Рабина
2 Алгоритм Миллера — Рабина
3 Алгоритм Миллера
4 Ссылки

[править] Свидетели простоты и теорема Рабина

Пусть $m$ — нечётное число большее 1. Число $m - 1$ однозначно представляется в виде $m-1 = 2^s \cdot t$ , где $t$ нечётно. Целое число $a$ , $1 < a < m$ , называется свидетелем простоты числа $m$ , если выполняются два условия:

$m$ не делится на $a$ ;
$a^t\equiv 1\pmod m$ или существует целое $k$ , $0\leq k<s$ , такое, что $a^{2^kt}\equiv -1\pmod m.$

Теорема Рабина утверждает, что составное нечётное число $m$ имеет не более $\varphi(m)/4$ различных свидетелей простоты, где $\varphi(m)$ — функция Эйлера.

[править] Алгоритм Миллера — Рабина

Алгоритм Миллера — Рабина параметризуется количеством раундов $r$ . Рекомендуется брать $r$ порядка величины $log 2 (m)$ , где $m$ — проверяемое число.

Для данного $m$ находятся такие целое число $s$ и целое нечётное число $t$ , что $m - 1 = 2 s t$ . Выбирается случайное число $a,1 < a < m$ . Если $a$ не является свидетелем простоты числа $m$ , то выдается ответ « $m$ составное», и алгоритм завершается. Иначе, выбирается новое случайное число $a$ и процедура проверки повторяется. После нахождения $r$ свидетелей простоты, выдается ответ « $m$ , вероятно, простое», и алгоритм завершается.

Из теоремы Рабина следует, что если $r$ случайно выбранных чисел оказались свидетелями простоты числа $m$ , то вероятность того, что $m$ составное, не превосходит $4 - r$ .

[править] Алгоритм Миллера

Изначальный алгоритм, предложенный Миллером, был детерминированным и состоял в проверке всех $a$ от $2$ до $70ln(m) 2$ . Алгоритм Миллера гарантированно распознает простые и составные числа при условии выполнения обобщённой гипотезы Римана. Алгоритм Миллера — Рабина не зависит от справедливости обобщённой гипотезы Римана, но является вероятностным.