Теоретико-числовые алгоритмы в криптографии

Обозначения......Page 7
Элементарные методы проверки простоты чисел......Page 12
Тесты на простоту для чисел специального вида......Page 15
101.21.2(N1)-методы проверки простоты чисел и построения больших простых чисел......Page 22
Алгоритм Конягина---Померанса......Page 28
Алгоритм Миллера......Page 32
Вероятностные тесты на простоту......Page 37
Современные методы проверки простоты чисел......Page 43
Заключение. Детерминированный полиномиальный алгоритм проверки простоты чисел......Page 48
Введение. Метод Ферма......Page 57
101.21.2(P-1)-метод Полларда......Page 60
101.21.2-метод Полларда......Page 62
Метод Шермана---Лемана......Page 65
Алгоритм Ленстры......Page 67
Алгоритм Полларда---Штрассена......Page 73
101.21.2(P+1)-метод Уильямса и его обобщения......Page 74
Методы Шэнкса......Page 75
Прочие методы. Заключение......Page 76
Введение......Page 77
Метод Диксона. Дополнительные стратегии......Page 78
Алгоритм Бриллхарта---Моррисона......Page 83
Квадратичное решето......Page 87
Методы Шнорра---Ленстры и Ленстры---Померанса......Page 92
Алгоритмы решета числового поля......Page 93
Заключение......Page 106
Введение. Эллиптические кривыеи их свойства......Page 107
Алгоритм Ленстры для факторизации целых чисел с помощью эллиптических кривых......Page 109
Вычисление порядка группы точек эллиптической кривой над конечным полем......Page 114
Тестирование чисел на простоту с помощью эллиптических кривых......Page 123
Заключение......Page 128
Введение. Детерминированные методы......Page 129
101.21.2-метод Полларда для дискретного логарифмирования......Page 131
Дискретное логарифмированиев простых полях......Page 133
Дискретное логарифмирование в полях Галуа......Page 137
Дискретное логарифмирование и решето числового поля......Page 140
Частное Ферма и дискретное логарифмирование по составному модулю......Page 145
Заключение......Page 160
Введение. Вероятностный алгоритм решения алгебраических уравнений в конечных полях......Page 162
Решение квадратных уравнений......Page 166
Алгоритм Берлекэмпа......Page 170
Метод Кантора---Цассенхауза......Page 175
Некоторые другие усовершенствования алгоритма Берлекэмпа......Page 178
Вероятностный алгоритм проверки неприводимости многочленовнад конечными полями......Page 181
Заключение......Page 184
Введение. Решетки и базисы......Page 186
LLL-приведенный базис и его свойства......Page 188
Алгоритм построения LLL-приведенного базиса решетки......Page 190
Алгоритм Шнорра---Ойхнера и целочисленный LLL-алгоритм......Page 194
Некоторые приложения LLL-алгоритма......Page 198
Алгоритм Фергюсона---Форкейда......Page 203
Заключение......Page 216
Введение......Page 217
LLL-алгоритм факторизации: разложение по простому модулю......Page 219
LLL-алгоритм факторизации: использование решеток......Page 220
LLL-алгоритм факторизации: подъем разложения......Page 225
LLL-алгоритм факторизации: полное описание......Page 228
Практичный алгоритм факторизации......Page 230
Факторизация многочленов с использованием приближенных вычислений......Page 232
Заключение......Page 238
Введение. Дискретное преобразование Фурье и его свойства......Page 239
Вычисление дискретногопреобразования Фурье......Page 241
Дискретное преобразование Фурье и умножение многочленов......Page 242
Дискретное преобразование Фурье и деление многочленов......Page 248
Применение дискретного преобразования Фурье в алгоритме Полларда---Штрассена......Page 251
Заключение......Page 253
Введение. Сложение и вычитание......Page 254
Умножение......Page 255
Деление......Page 259
Некоторые алгоритмымодулярной арифметики......Page 270
Введение......Page 274
Решение систем линейных уравнений в целых числах......Page 275
Гауссово и структурированное гауссово исключение......Page 280
Алгоритм Ланцоша......Page 281
Алгоритм Видемана......Page 287
Приложение. Сведения из теории чисел......Page 291
Предметный указатель......Page 299