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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тест Миллера – Рабина – проверка числа на простоту
5 (100%) 9 votes




Поделиться в соц. сетях:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">