Р. Крэндалл, К. Померанс | Простые числа. Криптографические и вычислительные аспекты (2011) [PDF]

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

От редактора перевода 5
Предисловие 7

Глава 1. Простые числа! 12
1.1 Прогресс и проблемы 12
1.1.1 Основные проблемы и теоремы 12
1.1.2 Технологический и алгоритмический прогресс 13
1.1.3 Бесконечность множества простых чисел 17
1.1.4 Асимптотические соотношения и порядковая терминология 20
1.1.5 Распределение простых чисел 22
1.2 Знаменитые гипотезы и загадки 26
1.2.1 Простые близнецы 27
1.2.2 k-кортежи простых и гипотеза H 30
1.2.3 Проблема Гольдбаха 31
1.2.4 Проблема выпуклости 33
1.2.5 Формула для простых чисел 34
1.3 Простые числа специального вида 35
1.3.1 Числа Мерсенна 35
1.3.2 Числа Ферма 41
1.3.3 Некоторые предположительно редкие простые числа 45
1.4 Аналитическая теория чисел 48
1.4.1 Дзета-функция Римана 48
1.4.2 Вычислительные достижения 53
1.4.3 L-функции Дирихле 55
1.4.4 Тригонометрические суммы 59
1.4.5 Гладкие числа 64
1.5 Упражнения 66
1.6 Проблемы для исследования 92

Глава 2. Аппарат теории чисел 102
2.1 Модулярная арифметика 102
2.1.1 Наибольший общий делитель и обратный элемент 102
2.1.2 Степени 105
2.1.3 Китайская теорема об остатках 106
2.2 Полиномиальная арифметика 108
2.2.1 Наибольший общий делитель многочленов 108
2.2.2 Конечные поля 111
2.3 Квадраты и корни 116
2.3.1 Квадратичные вычеты 116
2.3.2 Квадратные корни 120
2.3.3 Поиск корней многочленов 124
2.3.4 Представление числа квадратичной формой 127
2.4 Упражнения 129
2.5 Проблемы для исследования 134

Глава 3. Распознавание простых и составных чисел 138
3.1 Метод пробных делений 138
3.1.1 Признаки делимости 138
3.1.2 Метод пробных делений 139
3.1.3 Практические соображения 140
3.1.4 Теоретические соображения 141
3.2 Просеивание 142
3.2.1 Просеивание для распознавания простых чисел 142
3.2.2 Псевдокод для решета Эратосфена 143
3.2.3 Просеивание для создания таблицы делителей 144
3.2.4 Просеивание для полного разложения на множители 144
3.2.5 Просеивание для распознавания гладких чисел 145
3.2.6 Просеивание многочлена 146
3.2.7 Теоретические соображения 148
3.3 Распознавание гладких чисел 150
3.4 Псевдопростые числа 154
3.4.1 Псевдопростые числа Ферма 154
3.4.2 Числа Кармайкла 156
3.5 Вероятно простые числа и свидетели 158
3.5.1 Наименьший свидетель для n 163
3.6 Псевдопростые числа Люка 166
3.6.1 Псевдопростые числа Фибоначчи и Люка 166
3.6.2 Тест Грэнтхэма—Фробениуса 169
3.6.3 Реализация теста Люка и квадратичного теста Фробениуса 170
3.6.4 Теоретические соображения и более сильные тесты 173
3.6.5 Общий тест Фробениуса 175
3.7 Подсчет простых чисел 177
3.7.1 Комбинаторный метод 177
3.7.2 Аналитический метод 183
3.8 Упражнения 187
3.9 Проблемы для исследования 194

Глава 4. Доказательство простоты чисел 198
4.1 (n-1)-тест 198
4.1.1 Теорема Люка и тест Пепена 198
4.1.2 Частичное разложение на множители 200
4.1.3 Краткие сертификаты 204
4.2 (n+1)-тест 207
4.2.1 Тест Люка—Лемера 207
4.2.2 Улучшенный (n+1)-тест и объединенный (n2—1)-тест 210
4.2.3 Делители в классах вычетов 212
4.3 Проверка чисел на простоту при помощи конечного поля 216
4.4 Суммы Гаусса и Якоби 221
4.4.1 Тест, основанный на суммах Гаусса 221
4.4.2 Тест, основанный на суммах Якоби 227
4.5 Тест на простоту Агравала, Кайала и Саксены (AKS-тест) 228
4.5.1 Проверка на простоту с помощью корней из единицы 229
4.5.2 Сложность алгоритма 4.5.1 234
4.5.3 Проверка на простоту с помощью гауссовых периодов 236
4.5.4 Квартичный тест на простоту 242
4.6 Упражнения 247
4.7 Проблемы для исследования 253

Глава 5. Экспоненциальные алгоритмы разложения на множители 254
5.1 Метод квадратов 255
5.1.1 Метод Ферма 255
5.1.2 Метод Лемана 256
5.1.3 Отсев делителей 257
5.2 Методы Монте-Карло 258
5.2.1 Ро-метод Полларда для разложения на множители 259
5.2.2 Ро-метод Полларда для вычисления дискретных логарифмов 261
5.2.3 Лямбда-метод Полларда для вычисления дискретных логарифмов 263
5.3 Детские шаги, гигантские шаги 265
5.4 (p-1)-метод Полларда 267
5.5 Метод вычисления значений многочлена 269
5.6 Бинарные квадратичные формы 270
5.6.1 Основы теории квадратичных форм 270
5.6.2 Разложение на множители при помощи представления квадратичными формами 273
5.6.3 Композиция и группа классов 276
5.6.4 Амбиговы формы и разложение на множители 280
5.7 Упражнения 283
5.8 Проблемы для исследования 288

Глава 6. Субкспоненциальные алгоритмы разложения на множители 293
6.1 Разложение с помощью метода квадратичного решета 293
6.1.1 Базовый метод QS 293
6.1.2 Базовый алгоритм QS. Резюме 298
6.1.3 Быстрые матричные методы 301
6.1.4 Вариации больших простых 303
6.1.5 Многие полиномы 306
6.1.6 Автоматическая инициализация 308
6.1.7 Специальное квадратичное решето Жанга 310
6.2 Решето числового поля 313
6.2.1 Базовый алгоритм NFS: стратегия 313
6.2.2 Базовый метод NFS: векторы показателей 315
6.2.3 Базовый метод NFS: сложность 321
6.2.4 Базовый метод NFS: затруднения 323
6.2.5 Базовый метод NFS: квадратные корни 327
6.2.6 Базовый метод NFS: итоговый алгоритм 328
6.2.7 NFS: дальнейшие соображения 330
6.3 Строгое разложение на множители 338
6.4 Метод индекс-исчисления для дискретных логарифмов 340
6.4.1 Дискретные логарифмы в простых конечных полях 341
6.4.2 Вычисление дискретных логарифмов посредством гладких полиномов и гладких целых алгебраических чисел 343
6.5 Упражнения 345
6.6 Проблемы для исследования 354

Глава 7. Арифметика эллиптических кривых 358
7.1 Основы теории эллиптических кривых 358
7.2 Арифметика эллиптических кривых 363
7.3 Теоремы Хассе, Дойринга и Ленстры 374
7.4 Метод эллиптических кривых 376
7.4.1 Базовый алгоритм ECM 376
7.4.2 Оптимизации алгоритма ECM 381
7.5 Подсчет числа точек на эллиптической кривой 389
7.5.1 Метод Шенкса—Местре 389
7.5.2 Метод Шуфа 394
7.5.3 Метод Аткина—Морейна 401
7.6 Доказательство простоты при помощи эллиптических кривых 413
7.6.1 Тест на простоту Гольдвассер—Килиана 414
7.6.2 Тест на простоту Аткина—Морейна 417
7.6.3 Быстрое доказательство простоты при помощи эллиптических кривых (fastECPP) 420
7.7 Упражнения 420
7.8 Проблемы для исследования 427

Глава 8. Эти вездесущие простые числа 436
8.1 Криптография 436
8.1.1 Обмен ключом по Диффи-Хеллману 436
8.1.2 Криптосистема RSA 438
8.1.3 Криптосистемы на эллиптических кривых (криптосистемы ECC) 441
8.1.4 Протокол подбрасывания монеты 446
8.2 Генерирование случайных чисел 447
8.2.1 Модулярные методы 448
8.3 Методы квази-Монте-Карло 455
8.3.1 Теория дискрепанса 456
8.3.2 Специальные qMC-последовательности 459
8.3.3 Простые числа на Уолл-стрит? 461
8.4 Диофантов анализ 468
8.5 Квантовые вычисления 471
8.5.1 Квантовые машины Тьюринга (QTM) и интуиция 472
8.5.2 Квантовый алгоритм факторизации Шора 476
8.6 Простые числа в смежных областях, забавные и любопытные факты 478
8.7 Упражнения 485
8.8 Проблемы для исследования 491

Глава 9. Быстрые алгоритмы для работы с большими числами 498
9.1 Обзор «школьных» методов 498
9.1.1 Умножение 498
9.1.2 Возведение в квадрат 499
9.1.3 Операции div и mod 500
9.2 Усовершенствования в модулярной арифметике 502
9.2.1 Метод Монтгомери 503
9.2.2 Методы Ньютона 505
9.2.3 Модули особого вида 510
9.3 Возведение в степень 513
9.3.1 Простые двоичные схемы 514
9.3.2 Улучшения схем возведения в степень 516
9.4 Улучшения для НОД и поиска обратного элемента 520
9.4.1 Двоичные алгоритмы для НОД 520
9.4.2 Особые алгоритмы обращения 522
9.4.3 Рекурсивные алгоритмы для НОД в случае очень больших операндов 524
9.5 Умножение больших чисел 531
9.5.1 Методы Карацубы и Тоома—Кука 531
9.5.2 Алгоритмы вычисления преобразования Фурье 535
9.5.3 Теория сверток 548
9.5.4 Методы взвешенного дискретного преобразования (ВДП) 553
9.5.5 Теоретико-числовые преобразования 559
9.5.6 Метод Шёнхаге 563
9.5.7 Метод Нюссбаумера 565
9.5.8 Сложность алгоритмов умножения 568
9.5.9 Приложение к китайской теореме об остатках 569
9.6 Операции с многочленами 571
9.6.1 Умножение многочленов 571
9.6.2 Быстрое обращение многочленов и деление с остатком 573
9.6.3 Вычисление значений многочлена в наборе точек 576
9.7 Упражнения 580
9.8 Проблемы для исследования 598

Приложение. Псевдокод книги 604

Список литературы 611
Работы на русском языке 637
Список литературы, добавленной при переводе 638
Именной указатель 640
Предметный указатель 650
Оглавление 660

Файл, предлагаемый в раздаче, изготовлен из файла раздачи.
Что сделано по сравнению с той раздачей:
1) почищены страницы от небольшого мусора (лишь на паре страниц мусор бросается в глаза и портит вид страниц);

привожу сриншоты страниц с наиболее заметным мусором (не с целью принизить раздачу-предшественницу, но по требованию модератора раздела ):
верхний ряд - страницы из раздачи twingo, нижний ряд - те же страницы у меня.



2) растры ужаты (технология hd pdf) без потери качества (визуального), что привело к значительному уменьшению размера файла (с 70 мб. до 8,14 мб.);
3) добавлен OCR (не вычитан);
4) добавлены букмарки (оглавление).

Появление данной раздачи одобрено модератором раздела (twingo).