Аннотация 2
Введение 5
Глава 1. Теоретические основы критериев простоты целых чисел 6
1.1 Распределение простых чисел в натуральном ряду 6
1.2 Критерии простоты 10
Глава 2. Тесты простоты целых чисел 16
2.1 Вероятностные тесты простоты 16
2.1.1 Тест простоты Ферма 17
2.1.2 Тест простоты Соловея и Штрассена 20
2.1.3 Тест простоты Соловея и Штрассена 23
2.2 Полиномиальный тест распознавания простоты 27
Глава 3. Алгоритмы тестов простоты целых чисел 32
3.1 Алгоритм теста Ферма 32
3.2 Алгоритм теста Соловея и Штрассена 33
3.3 Алгоритм теста Миллера и Рабина 35
Заключение 37
Список используемых источников 38
Приложения 40
Проблема защиты информации путем ее преобразования давно беспокоила человеческий разум. Криптография - того же возраст, что и история человеческого языка. Изначально сама запись была своего рода криптографической системой, поскольку в древних обществах она принадлежала только элите.
Простые числа применяются в криптосистемах с открытым ключом, поэтому вопрос об определении простоты числа является актуальной задачей.
Объект исследования - простые целые числа.
Предмет исследования - критерии простоты целых чисел.
Целью данной работы являются алгоритмы проверки простоты целых чисел.
Для реализации эти цели формулируются задачи:
1. Описание теоретических основ критериев простоты целых чисел;
2. Построение алгоритмов проверки простоты целых чисел;
3. Реализация алгоритмов проверки простоты;
Во введении обосновывается актуальность темы исследования, формулируется цель, а также задачи, вытекающие из постановки цели.
Первая глава повешена теоретическим основам критериев простоты целых чисел.
Во второй главе рассматриваются тесты простоты целых чисел.
В третьей главе реализуются алгоритмы тестов простоты целых чисел.
Бакалаврская работа посвящена алгоритмам проверки простоты целых чисел. Простые числа используется в криптосистемах с открытым ключом.
Целью данной работы были алгоритмы простоты целых чисел. Для этого в работе были рассмотрены следующие вопросы: распределение простоты чисел в натуральном ряду, критерии простоты. Тесты основаны на некоторых критериях простоты. Описаны следующие тесты простоты целых чисел: вероятностные тесты простоты, тест простоты Ферма, тест простоты Соловея и Штрассена, тест простоты Миллера и Рабина, полиномиальный тест распознавания простоты.
Результатом работы являются реализации алгоритмов тестов Ферма, Соловея и Штрасена, Миллера и Рабина на языке C++.
Задачи, выполненные в ходе данной работы, позволили в итоге реализовать критерии проверки простоты целых чисел и понять в каких аспектах и какой из, них имеет преимущество.
Подводя итог, можно констатировать, что тест Миллера-Рабина считается более результативным и универсальным из тех, которые рассматриваются в этой бакалаврской работе.
