Читать онлайн «Элементы теории чисел и криптозащита: Учебное пособие для вузов. Часть 2»
Автор Воронков Б.Н.
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ
И КРИПТОЗАЩИТА
Учебное пособие для вузов
Часть 2
Составители:
Б. Н. Воронков,
А. С. Щеголеватых
Издательско-полиграфический центр
Воронежского государственного университета
2008
Утверждено учебно-методическим советом факультета прикладной матема-
тики, информатики и механики 11 сентября 2008 г. , протокол № 1
Рецензент К. П. Лазарев
Учебное пособие подготовлено на кафедре технической кибернетики и ав-
томатического регулирования факультета прикладной математики, инфор-
матики и механики Воронежского государственного университета. Рекомендуется для студентов 4-го курса дневного отделения и 4-го курса ве-
чернего отделения. Для специальности 010501 – Прикладная математика и информатика
2
Cодержание
Предисловие ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 4
1. Простые числа ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 4
2. Наибольший общий делитель и наименьшее общее кратное ... ... ... . . 5
3. Алгоритм Евклида. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 8
4. [х] и применения ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 16
5. Дополнение... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 22
6. Получение простых чисел... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 28
7. Аппроксимация функции π(x) ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 33
8. Решето Эратосфена... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 34
9. Сравнения ... ... ... ... ...
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 36
10. Инверсии по mod m и решения соответствующих сравнений ... . . 39
11. Дальнейшие примеры сравнений ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 44
12. Степени ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 48
13. Алгоритм Хэда умножения по mod m... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 53
14. Псевдопростые числа ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 54
15. Теорема Вильсона ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 58
16. Тест Миллера... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 59
17. Вероятностное тестирование на простоту ... ... ... ... ... ... ... ... ... ... ... ... . 63
18. Функция Эйлера... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 65
19. Теорема Эйлера и понятие порядка ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 70
20.
