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

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

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

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

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

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

1. m не делится на a;
2. или существует целое k, , такое, что

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

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

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

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

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

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

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

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

Если число a является свидетелем простоты составного нечетного числа m, то число m в свою очередь называется сильно псевдопростым по основанию a. Если число m является сильно псевдопростым по основанию a, то оно также является псевдопростым по основанию a.

[править] Ссылки

• «Как отличить составное число от простого», глава 4.4 из книги «Введение в криптографию» под редакцией В. В. Ященко
• С. Б. Гашков, «Упрощенное обоснование вероятностного теста Миллера — Рабина для проверки простоты чисел»