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

О.Н. Василенко
20.05.2005 | 13:59
Монография

Москва, МЦНМО, 2003. - 328 с.

ISBN 5-94057-103-4

В монографии представлено современное состояние алгоритмической теории чисел, имеющей важные приложения в криптографии.

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



Оглавление

Предисловие ... 7
Обозначения ... 10
Глава 1. Тестирование чисел на простоту и построение больших простых чисел ... 12
1.1. Введение ... 12
1.2. Элементарные методы проверки простоты чисел ... 12
1.3. Тесты на простоту для чисел специального вида ... 15
1.4. (N+1)-методы проверки простоты чисел и построения больших простых чисел ... 22
1.5. Алгоритм Конягина-Померанса ... 28
1.6. Алгоритм Миллера ... 32
1.7. Вероятностные тесты на простоту ... 37
1.8. Современные методы проверки простоты чисел ... 43
1.9. Заключение. Детерминированный полиномиальный алгоритм проверки простоты чисел ... 48
Глава 2. Факторизация целых чисел с экспоненциальной сложностью ... 57
2.1. Введение. Метод Ферма ... 57
2.2. (P-1)-метод Полларда ... 60
2.3. r-метод Полларда ... 62
2.4. Метод Шермана-Лемана ... 65
2.5. Алгоритм Ленстры ... 67
2.6. Алгоритм Полларда-Штрассена ... 73
2.7. (P+1)-метод Уильямса и его обобщения ... 74
2.8. Методы Шэнкса ... 75
2.9. Прочие методы. Заключение ... 76
Глава 3. Факторизация целых чисел с субэкспоненциальной сложностью ... 77
3.1. Введение ... 77
3.2. Метод Диксона. Дополнительные стратегии ... 78
3.3. Алгоритм Бриллхарта-Моррисона ... 83
3.4. Квадратичное решето ... 87
3.5. Методы Шнорра-Ленстры и Ленстры-Померанса ... 92
3.6. Алгоритмы решета числового поля ... 93
3.7. Заключение ... 106
Глава 4. Применение кривых для проверки простоты и факторизации ... 107
4.1. Введение. Эллиптические кривые и их свойства ... 107
4.2. Алгоритм Ленстры для факторизации целых чисел с помощью эллиптических кривых ... 109
4.3. Вычисление порядка группы точек эллиптической кривой над конечным полем ... 114
4.4. Тестирование чисел на простоту с помощью эллиптических кривых ... 123
4.5. Заключение ... 128
Глава 5. Алгоритмы дискретного логарифмирования ... 129
5.1. Введение. Детерминированные методы ... 129
5.2. r-метод Полларда для дискретного логарифмирования ... 131
5.3. Дискретное логарифмирование в простых полях ... 133
5.4. Дискретное логарифмирование в полях Галуа ... 137
5.5. Дискретное логарифмирование и решето числового поля ... 140
5.6. Частное Ферма и дискретное логарифмирование по составному модулю ... 145
5.7. Заключение ... 160
Глава 6. Факторизация многочленов над конечными полями ... 162
6.1. Введение. Вероятностный алгоритм решения алгебраических уравнений в конечных полях ... 162
6.2. Решение квадратных уравнений ... 166
6.3. Алгоритм Берлекэмпа ... 170
6.4. Метод Кантора-Цассенхауза ... 175
6.5. Некоторые другие усовершенствования алгоритма Берлекэмпа ... 178
6.6. Вероятностный алгоритм проверки неприводимости многочленов над конечными полями ... 181
6.7. Заключение ... 184
Глава 7. Приведенные базисы решеток и их приложения ... 186
7.1. Введение. Решетки и базисы ... 186
7.2. LLL-приведенный базис и его свойства ... 188
7.3. Алгоритм построения LLL-приведенного базиса решетки ... 190
7.4. Алгоритм Шнорра-Ойхнера и целочисленный LLL-алгоритм ... 194
7.5. Некоторые приложения LLL-алгоритма ... 198
7.6. Алгоритм Фергюсона-Форкейда ... 203
7.7. Заключение ... 216
Глава 8. Факторизация многочленов над полем рациональных чисел ... 217
8.1. Введение ... 217
8.2. LLL-алгоритм факторизации: разложение по простому модулю ... 219
8.3. LLL-алгоритм факторизации: использование решеток ... 220
8.4. LLL-алгоритм факторизации: подъем разложения ... 225
8.5. LLL-алгоритм факторизации: полное описание ... 228
8.6. Практичный алгоритм факторизации ... 230
8.7. Факторизация многочленов с использованием приближенных вычислений ... 232
8.8. Заключение ... 238
Глава 9. Дискретное преобразование Фурье ... 239
9.1. Введение. Дискретное преобразование Фурье и его свойства ... 239
9.2. Вычисление дискретного преобразования Фурье ... 241
9.3. Дискретное преобразование Фурье и умножение многочленов ... 242
9.4. Дискретное преобразование Фурье и деление многочленов ... 248
9.5. Применение дискретного преобразования Фурье в алгоритме Полларда-Штрассена ... 251
9.6. Заключение ... 253
Глава 10. Целочисленная арифметика многократной точности ... 254
10.1. Введение. Сложение и вычитание ... 254
10.2. Умножение ... 255
10.3. Деление ... 259
10.4. Некоторые алгоритмы модулярной арифметики ... 270
Глава 11. Решение систем линейных уравнений над конечными полями ... 274
11.1. Введение ... 274
11.2. Решение систем линейных уравнений в целых числах ... 275
11.3. Гауссово и структурированное гауссово исключение ... 280
11.4. Алгоритм Ланцоша ... 281
11.5. Алгоритм Видемана ... 287
11.6. Другие методы. Заключение ... 291
Приложение. Сведения из теории чисел 292
Литература ... 303
Предметный указатель ... 322



Источник: Cryptography.Ru