— вероятностный
полиномиальный тест простоты. Тест Миллера — Рабина позволяет эффективно определять,
является ли данное число составным. Однако, с его помощью нельзя строго
доказать простоту числа. Тем не менее тест Миллера — Рабина часто используется
в криптографии для получения больших случайных простых чисел.
Свидетели простоты и теорема
Рабина
Пусть m — нечётное число
большее 1. Число m - 1 однозначно представляется в виде , где t нечётно. Целое
число a, 1 < a < m, называется свидетелем простоты числа m, если
выполняются два условия:
m не делится на a; или
существует целое k, , такое, что
Теорема Рабина утверждает,
что составное нечётное число m имеет не более
различных свидетелей простоты, где
— функция Эйлера.
Алгоритм Миллера — Рабина
Алгоритм Миллера — Рабина
параметризуется количеством раундов r. Рекомендуется брать r порядка величины
log2(m), где m — проверяемое число.
Для данного m находятся такие
целое число s и целое нечётное число t, что m − 1 = 2st. Выбирается случайное
число a,1 < a < m. Если a не является свидетелем простоты числа m, то
выдается ответ «m составное», и алгоритм завершается. Иначе, выбирается новое
случайное число a и процедура проверки повторяется. После нахождения r
свидетелей простоты, выдается ответ «m, вероятно, простое», и алгоритм
завершается.
---------------
Алгоритм может быть записан
на псевдокоде следующим образом:
Ввод: m > 2, нечётное
натуральное число, которое необходимо проверить на простоту;
r, параметр, определяющий точность
теста.
Вывод: составное, означает,
что m точно составное;
вероятно простое, означает, что m с
высокой вероятностью является простым
Представить m − 1 в виде
2s·t, где t нечётно, можно сделать последовательным делением m - 1 на 2.
цикл А: повторить r раз:
Выбрать случайное a в диапазоне [2, m − 2]
x ← at mod m
если x = 1 или x = m − 1 то перейти на
следующую итерацию цикла А
для r = 1 .. s − 1
x ← x2 mod m
если x = 1 то вернуть составное
если x = m − 1 то перейти на следующую
итерацию цикла А
вернуть составное
вернуть вероятно простое
-----------------------
Из теоремы Рабина следует,
что если r случайно выбранных чисел оказались свидетелями простоты числа m, то
вероятность того, что m составное, не превосходит 4 - r.
Алгоритм Миллера
Изначальный алгоритм,
предложенный Миллером, был детерминированным и состоял в проверке всех a от 2
до 70ln(m)2. Алгоритм Миллера гарантированно распознает простые и составные
числа при условии выполнения обобщённой гипотезы Римана. Алгоритм Миллера —
Рабина не зависит от справедливости обобщённой гипотезы Римана, но является
вероятностным.
Сильно псевдопростые числа
Если число a является
свидетелем простоты составного нечетного числа m, то число m в свою очередь
называется сильно псевдопростым по основанию a. Если число m является сильно
псевдопростым по основанию a, то оно также является псевдопростым по основанию
a.
|