ОСТОРОЖНО МОШЕННИКИ! В последнее время в соиальных сетях учстились случаи педложения помощи в написании прогамм от лиц, прикрвающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в псторонних группах ВК. Для связи с нами используйте исключительно эти контакт: vscoderu@yandex.ru, https://vk.com/vscode


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


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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

5/5 - (15 голосов)



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

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

Ваш адрес email не будет опубликован.