ВУЗ:
Составители:
Рубрика:
3
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. Тесты на простоту............................................................................. 75
21. Криптосистема RSA (Rivest R., Shamir A., Adleman L.) ............... 79
22. Применение уравнения Пелля......................................................... 82
23. Примитивные корни ......................................................................... 83
Библиография.......................................................................................... 95
