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

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

Содержание

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

Пусть 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 порядка величины log2(m), где m — проверяемое число.

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

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

Алгоритм Миллера

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

Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home