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

Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 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

загрузка...
Поделиться ссылкой:
  • Добавить ВКонтакте заметку об этой странице
  • Мой Мир
  • Facebook
  • Twitter
  • LiveJournal
  • В закладки Google
  • Яндекс.Закладки
  • Сто закладок
  • Blogger
  • Блог Li.ру
  • Блог Я.ру
  • Одноклассники
  • RSS

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Наш сайт находят по фразам: