Введение 3
Некоторые элементы теории чисел 4

Вычисление наибольшего общего делителя 9
Алгоритм Евклида 9
Бинарный алгоритм Евклида 9
Расширенный алгоритм Евклида 10
Вариант расширенного алгоритма Евклида 10

Отношение сравнимости 14
Свойства сравнений 14

Модулярная арифметика 16
Вычисление aͯ mod n 16

Классы 17
Полная и приведенная система вычетов 18
Функция Эйлера 19
Сравнения первой степени 24

Криптография с открытым ключом 27
Криптосистема RSA 28
Формирование системы RSA 30
Алгоритм шифрования 30
Алгоритм дешифрования 30
Цифровая подпись 30

Степенные вычеты 35
Первообразные корни 46
Индексы 47

Алгоритмы дискретного логарифмирования 53
Задача дискретного логарифмирования в конечном поле 53
ρ-метод Полларда 53
Схема Эль–Гамаля 55
Схема Шнорра 56

Китайская теорема об остатках 59
Сравнения степеней выше первого 63
Сравнения по составному модулю 70
Двучленные сравнения 72

Сравнения второй степени по простому модулю и квадратичные вычеты 76
Алгоритм вычисления символа Якоби 84

Вычисление квадратных корней по модулю 88
Случай простого модуля 88
Случай составного модуля 91
Вычисление квадратных корней по составному модулю 96

Цифровая подпись Фиата–Шамира 98
Простые числа 100

Проверка на простоту 102
Пробное деление 102
Решето Эратосфена 102
Тест на основе малой теоремы Ферма 103
Схема алгоритма на базе малой теоремы Ферма 103
Тест Соловея–Штрассена 104
Схема алгоритма на базе малой теоремы Ферма 104
Тест Рабина–Миллера 104
Схема алгоритма Рабина–Миллера 105
Построение больших простых чисел и детерминированные алгоритмы проверки чисел на простоту 106
Проверка чисел Мерсенна на простоту 107

Разложение чисел на множители 108
Метод пробного деления 108
Факторизация Ферма 109
ρ-метод Полларда 111
(р–1)-метод Полларда 113

Арифметические операции над большими числами 116
Сложение 116
Вычитание 117
Умножение 117
Деление 118
Модифицированное деление столбиком 118
Модульное умножение 119
Метод Монтгомери 119

Библиографический список 122

Приложение 1. Группы, кольца, поля 123
Группы 123
Кольца. Поля. Многочлены над полем 127
Приложение 2. Реализация алгоритмов 132
Описание 132
Решение сравнения 132
Алгоритм Евклида 136
Бинарный алгоритм Евклида 138
Расширенный алгоритм Евклида 139
Вычисление символа Якоби 141
Вычисление символа Лежандра 143
Решето Эратосфена 145
Пробное деление 146
Тест на основе малой теоремы Ферма 147
Тест Соловея–Штрассена 149
Тест Рабина–Миллера 151
Метод p–1 Полларда 153
Метод ρ-Полларда 155
Факторизация Ферма (разность квадратов) 157