admin / 03.11.2019

Миллера рабина

В статье разберем алгоритм под названием Тест Миллера – Рабина. Он применяется при проверке числа на простоту.

Выполнять проверку числа на простоту требуется часто. Данная операция распространена и в задачах, и в алгоритмах.

Небольшое число легко проверить на простоту – достаточно в цикле перебрать все числа от 2 до N – 1 и проверить не делится ли N на них без остатка.

Но когда речь заходит об очень больших числах (содержащих в своем составе десятки разрядов) – такой подход не годится: вычисления займут большое время (часы, сутки).

В данном случае применяют специальные алгоритмы, называемые тестами на простоту. Рассмотрим один из таких тестов, он называется Тест Миллера – Рабина.

Тест Миллера – Рабина – описание алгоритма

Алгоритм является вероятностно-полиномиальным, т. е. быстро вычислимым (за приемлемое время) и дающим ответ с высокой точностью. При этом, жертвуя временем, можно добиться любой требуемой точности.

Таким образом, отвечая на вопрос “является ли число простым?”, тест Миллера – Рабина дает один из двух вариантов ответа: “число составное” или “вероятно простое“.

Выполнив тест и получив положительный ответ, можно с большой вероятностью (но не 100%-й) утверждать, что число простое.

Ниже приведено описание алгоритма теста Миллера – Рабина на псевдокоде:

Тест Миллера – Рабина – реализация алгоритма

Приведем реализацию теста на языке программирования C#. Код снабжен комментариями.

Метод возвращает логическое значение true, если число n “вероятно простое”, и false, если число n является составным.

C#

В реализации используется структура BigInteger. Она позволяет хранить произвольно большие целые числа.

Тест Миллера – Рабина – видеоурок

В видео приводится разбор алгоритма и его реализация на C#.

Тест Миллера – Рабина – проверка числа на простоту 5 (100%) 11 votes
c#, Алгоритм, Видео, Видеоурок, Простое число, Реализация, Урок

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

Эта статья находится в разработке!

Можно существенно улучшить тест Ферма, заметив, что если — простое нечетное, то для есть только два квадратных корня по модулю и . Таким образом, квадратный корень из равен . Если опять нечетно, то мы можем снова извлечь корень и так далее. Первый вариант алгоритма предлагает использовать только одно деление:

Тест Леманна

Если для какого-либо целого числа меньшего не выполняется условие , то число — составное. Если это условие выполняется, то число — возможно простое, причем вероятность ошибки не превышает .

Этот тест можно естественным образом улучшить, если извлекать корень по модулю не один раз, а столько, сколько получится.

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

Запишем в виде , где нечетно, а неотрицательно: называется сильно возможно простым по основанию , если выполняется одно из двух условий:

Определение:

Пусть — нечетное число, большее . Число однозначно представляется в виде , где четно. Целое число называется свидетелем простоты числа , если выполняется два условия:

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

FILED UNDER : Статьи

Submit a Comment

Must be required * marked fields.

:*
:*