Реализация упрощённого варианта генерации «сильных» простых чисел с использованием вероятностного теста рабина-миллера(для искусственн

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

ВВЕДЕНИЕ…………………………………………………………………………..6
1 ИСПОЛЬЗУЕМЫЕ МЕТОДЫ И АЛГОРИТМЫ………………………………..7
1.1 Общие сведения о простых числах…………………………………………..7
1.2 Способы генерации простых чисел………………………………………...12
1.3 Методы проверки чисел на простоту………………………………………13
1.3.1 Метод пробных делений………………………………………………13
1.3.2 Проверка способом «решето Эратосфена»…………………………..14
1.3.3 Метод на основе теоремы Вильсона………………………………….15
1.3.4 Проверка с помощью вероятностных тестов……………………...…15 1.4 Алгоритм теста Рабина-Миллера и практические соображения программной реализации…………………………………………………………………………..17
2 ОПИСАНИЕ ПРОГРАММЫ…………………………………………………….19
2.1Общие сведения……………………………………………………………...19
2.2Функциональное назначение программы………………………………….19
2.3 Описание логической структуры…………………………………………..20
2.3.1 Блок-схема алгоритма…………………………………………………20
2.3.2 Структура программы с описанием функций………………………..21
2.4 Используемые технические средства ……………………………………..21
2.5 Входные и выходные данные………………………………………………21
ВЫВОДЫ…………………………………………………………………………...23
ПЕРЕЧЕНЬ ССЫЛОК……………………………………………………………...24
ПРИЛОЖЕНИЕ А Код программы……………………………………………….25
ПРИЛОЖЕНИЕ Б Результаты работы программы………………………………31