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

О. Н. ВАСИЛЕНКО5-94057-103-4

В монографии представлено современное состояние алгоритмической теории чисел, имеющей важные приложения в криптографии.Предназначено для студентов старших курсов и аспирантов математических факультетов вузов, а также для специалистов, желающих познакомиться с последними достижениями в данной области.

---

Table of contents :
Обозначения……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