Василенко О. Н. Теоретико-числовые алгоритмы в криптографии ОНЛАЙН

Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М., 2003. —328 с.
В монографии представлено современное состояние алгоритмической теории чисел, имеющей важные приложения в криптографии. Предназначено для студентов старших курсов и аспирантов математических факультетов вузов, а также для специалистов, желающих познакомиться с последними достижениями в данной области.
Оглавление
Предисловие ................................................................................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. (Р— 1)-метод Полларда......................................................60
§2.3. р-метод Полларда................................................................62
§2.4. Метод Шермана—Лемана..................................................65
§2.5. Алгоритм Ленстры ..............................................................67
§2.6. Алгоритм Полларда—Штрассена ....................................73
§2.7. (P-h 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. Заключение ...................................................................107
Глава 4. Применение кривых для проверки простоты и факторизации........................108
§4.1. Введение. Эллиптические кривые и их свойства............108
§4.2. Алгоритм Ленстры для факторизации целых чисел с помощью эллиптических кривых.......110
§ 4.3. Вычисление порядка группы точек эллиптической кривой над конечным полем ........115
§4.4. Тестирование чисел на простоту с помощью эллиптических кривых.....................124
§4.5. Заключение ....................................................129
Глава 5. Алгоритмы дискретного логарифмирования ............130
§5.1. Введение. Детерминированные методы............................130
§ 5.2. р-метод Полларда для дискретного логарифмирования 132
§5.3. Дискретное логарифмирование в простых полях ..........134
§5.4. Дискретное логарифмирование в полях Галуа................138
§ 5.5. Дискретное логарифмирование и решето числового поля 141
§ 5.6. Частное Ферма и дискретное логарифмирование по составному модулю.................146
§5.7. Заключение ...............................................................161
Глава 6. Факторизация многочленов над конечными полями 163
§ 6.1. Введение. Вероятностный алгоритм решения алгебраических уравнений в конечных полях ..163
§6.2. Решение квадратных уравнений........................................167
§6.3. Алгоритм Берлекэмпа ........................................................171
§6.4. Метод Кантора—Цассенхауза..........................................176
§6.5. Некоторые другие усовершенствования алгоритма Берлекэмпа ................179
§6.6. Вероятностный алгоритм проверки неприводимости многочленов над конечными полями........182
§6.7. Заключение ......................................................................185
Глава 7. Приведенные базисы решеток и их приложения .. 187
§7.1. Введение. Решетки и базисы ............................................187
§7.2. LLL-приведенный базис и его свойства..........................189
§7.3. Алгоритм построения LLL-приведенного базиса решетки .......191
§7.4. Алгоритм Шнорра—Ойхнера и целочисленный LLL-алгоритм.........................196
§7.5. Некоторые приложения LLL-алгоритма..........................199
§ 7.6. Алгоритм Фергюсона—Форкейда ....................................204
§ 7.7. Заключение ...........................................................217
Глава 8. Факторизация многочленов над полем рациональных чисел ...................218
§8.1. Введение..............................................................218
§ 8.2. LLL-алгоритм факторизации: разложение по простому модулю ...................220
§8.3. LLL-алгоритм факторизации: использование решеток 221
§8.4. LLL-алгоритм факторизации: подъем разложения .... 226
§8.5. LLL-алгоритм факторизации: полное описание..............229
§8.6. Практичный алгоритм факторизации................................231
§8.7. Факторизация многочленов с использованием приближенных вычислений ........233
§8.8. Заключение ....................................................239
Глава 9. Дискретное преобразование Фурье............................240
§9.1. Введение. Дискретное преобразование Фурье и его свойства .....................240
§9.2. Вычисление дискретного преобразования Фурье ..........242
§9.3. Дискретное преобразование Фурье и умножение многочленов ....................243
§9.4. Дискретное преобразование Фурье и деление многочленов ..................249
§9.5. Применение дискретного преобразования Фурье в алгоритме Полларда—Штрассена......252
§ 9.6. Заключение ..................................................................254
Глава 10. Целочисленная арифметика многократной точности 255
§ 10.1. Введение. Сложение и вычитание ....................................255
§ 10.2. Умножение................................................................256
§10.3. Деление..................................................................260
§ 10.4. Некоторые алгоритмы модулярной арифметики ............271
Глава 11. Решение систем линейных уравнений над конечными полями ...............275
§11.1. Введение................................................................275
§ 11.2. Решение систем линейных уравнений в целых числах . 276
§11.3. Гауссово и структурированное гауссово исключение .. 281
§ 11.4. Алгоритм Ланцоша..................................................282
§11.5. Алгоритм Видемана .......................................................288
§ 11.6. Другие методы. Заключение..............................................292
Приложение. Сведения из теории чисел ......................................293
Литература...................................................................304
Предметный указатель..........................................................323