Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

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

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

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

  1. m не делится на a;
  2. 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 до 70 \ln(m)^2. Алгоритм Миллера гарантированно распознает простые и составные числа при условии выполнения обобщённой гипотезы Римана. Алгоритм Миллера — Рабина не зависит от справедливости обобщённой гипотезы Римана, но является вероятностным.

СсылкиПравить

Викия-сеть

Случайная вики