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

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

  Простые числа дразнят воображение начинающего математика: ведь даже ребенку можно объяснить, что такое простое число, но в то же время есть ряд несложных на вид задач, над которыми лучшие умы человечества ломают головы на протяжении нескольких тысячелетий. Во второе английское издание книги «Простые числа» авторы Ричард Крэндалл и Карл Померане включили актуальный материал из теоретической, вычислительной и алгоритмической областей. Это издание оказалось очень успешным. В нем излагаются новые результаты, которые включают AKS-тест для распознавания простых чисел, вычислительные свидетельства справедливости гипотезы Римана, быстрый бинарный алгоритм вычисления наибольшего общего делителя, неоднородные быстрые преобразования Фурье и многое другое. Авторы также приводят новые рекорды из вычислительной области и дают обзор последних результатов в теории простых чисел, например интереснейшее доказательство существования сколь угодно длинной конечной арифметической прогрессии, составленной из простых чисел, и полное решение проблемы Каталана. Во второе издание добавлены также многочисленные упражнения.
Эту книгу можно изучать на разных уровнях. Для тех, кто хочет получить общее впечатление об этой красивой науке и об основных методах работы с простыми числами, книга является прекрасным введением в предмет. Для тех же, кто хочет глубже вникнуть в подробности новейших методов вычислений с простыми числами, в книге приводится соответствующий материал, а также ссылки на обширную литературу по теме. Студенты смогут проверить свое понимание с помощью интересных упражнений, подчас занимательных и нестандартных. Наконец, для тех, кто хочет начать или углубить свои исследования по вычислительной теории простых чисел, по тексту и в упражнениях щедро разбросаны многочисленные нерешенные проблемы, которые предоставляют богатую почву для дальнейшего анализа.
Книга будет интересна студентам, преподавателям и научным работникам, специализирующимся в области теории чисел и дискретной математики, а также специалистам в области криптографии и защиты информации.




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

В нашей книге, говоря о вычислительной сложности алгоритмов, мы почти всегда будем придерживаться обозначения «О», несмотря на то, что некоторые авторы обозначают битовую и операционную сложности через Оb и Оор соответственно. Поэтому, когда сложность алгоритма записана через О, мы для каждого случая будем по возможности указывать, какую именно сложность мы имеем в виду. Необходимо учитывать, что эти величины не обязательно пропорциональны, поскольку это зависит оттого, производятся ли «операции» в поле, являются они сложением, умножением или сравнением (что имеет место для условных операторов). Например, в гл. 9 мы увидим, что базовый метод умножения с помощью БПФ требует 0(DlnD) операций над числами с плавающей точкой, каждое из которых имеет D разрядов (по подходящему основанию), в то время как существуют методы, имеющие битовую сложность 0(п ln п ln ln n), где п обозначает общее число битов во множителях. В этом случае отсутствует явная пропорциональность; соотношения между числом разрядов, основанием и битовым размером n нетривиальны (особенно когда в вычислениях возникают ошибки, связанные с плавающей точкой) и т.д.

Оглавление.
От редактора перевода.
Предисловие.
Глава 1. ПРОСТЫЕ ЧИСЛА!.
1.1. Прогресс и проблемы.
1.1.1. Основные проблемы и теоремы.
1.1.2. Технологический и алгоритмический прогресс.
1.1.3. Бесконечность множества простых чисел.
1.1.4. Асимптотические соотношения и порядковая терминология.
1.1.5. Распределение простых чисел.
1.2. Знаменитые гипотезы и загадки.
1.2.1. Простые близнецы.
1.2.2. k-кортежи простых и гипотеза Н.
1.2.3. Проблема Гольдбаха.
1.2.4. Проблема выпуклости.
1.2.5. Формула для простых чисел.
1.3. Простые числа специального вида.
1.3.1. Числа Мерсенна.
1.3.2. Числа Ферма.
1.3.3. Некоторые предположительно редкие простые числа.
1.4. Аналитическая теория чисел.
1.4.1. Дзета-функция Римана.
1.4.2. Вычислительные достижения.
1.4.3. L-функции Дирихле.
1.4.4. Тригонометрические суммы.
1.4.5. Гладкие числа.
1.5. Упражнения.
1.6. Проблемы для исследования.
Глава 2. АППАРАТ ТЕОРИИ ЧИСЕЛ.
2.1. Модулярная арифметика.
2.1.1. Наибольший общий делитель и обратный элемент.
2.1.2. Степени.
2.1.3. Китайская теорема об остатках.
2.2. Полиномиальная арифметика.
2.2.1. Наибольший общий делитель многочленов.
2.2.2. Конечные поля.
2.3. Квадраты и корни.
2.3.1. Квадратичные вычеты.
2.3.2. Квадратные корни.
2.3.3. Поиск корней многочленов.
2.3.4. Представление числа квадратичной формой.
2.4. Упражнения.
2.5. Проблемы для исследования.
Глава 3. РАСПОЗНАВАНИЕ ПРОСТЫХ И СОСТАВНЫХ ЧИСЕЛ.
3.1. Метод пробных делений.
3.1.1. Признаки делимости.
3.1.2. Метод пробных делений.
3.1.3. Практические соображения.
3.1.4. Теоретические соображения.
3.2. Просеивание.
3.2.1. Просеивание для распознавания простых чисел.
3.2.2. Псевдокод для решета Эратосфена.
3.2.3. Просеивание для создания таблицы делителей).
3.2.4. Просеивание для полного разложения на множители.
3.2.5. Просеивание для распознавания гладких чисел.
3.2.6. Просеивание многочлена.
3.2.7. Теоретические соображения.
3.3. Распознавание гладких чисел.
3.4. Псевдопростые числа.
3.4.1. Псевдопростые числа Ферма.
3.4.2. Числа Кармайкла.
3.5. Вероятно простые числа и свидетели.
3.5.1. Наименьший свидетель для n.
3.6. Псевдопростые числа Люка.
3.6.1. Псевдопростые числа Фибоначчи и Люка.
3.6.2. Тест Грэнтхэма—Фробениуса.
3.6.3. Реализация теста Люка и квадратичного теста Фробениуса.
3.6.4. Теоретические соображения и более сильные тесты.
3.6.5. Общий тест Фробениуса.
3.7. Подсчет простых чисел.
3.7.1. Комбинаторный метод.
3.7.2. Аналитический метод.
3.8. Упражнения.
3.9. Проблемы для исследования.
Глава 4. ДОКАЗАТЕЛЬСТВО ПРОСТОТЫ ЧИСЕЛ.
4.1. (n - 1)-тест.
4.1.1. Теорема Люка и тест Пепена.
4.1.2. Частичное разложение на множители.
4.1.3. Краткие сертификаты.
4.2 (n + 1)-тест.
4.2.1. Тест Люка—Лемера.
4.2.2. Улучшенный (n + 1)-тест и объединенный (n2 — 1)-тест.
4.2.3. Делители в классах вычетов.
4.3. Проверка чисел на простоту при помощи конечного поля.
4.4. Суммы Гаусса и Якоби.
4.4.1. Тест, основанный на суммах Гаусса.
4.4.2. Тест, основанный на суммах Якоби.
4.5. Тест на простоту Агравала, Кайала и Саксены (AKS-тест).
4.5.1. Проверка на простоту с помощью корней из единицы.
4.5.2. Сложность алгоритма 4.5.1.
4.5.3. Проверка на простоту с помощью гауссовых периодов.
4.5.4. Квартичный тест на простоту.
4.6. Упражнения.
4.7. Проблемы для исследования.
Глава 5. ЭКСПОНЕНЦИАЛЬНЫЕ АЛГОРИТМЫ РАЗЛОЖЕНИЯ НА МНОЖИТЕЛИ.
5.1. Метод квадратов.
5.1.1. Метод Ферма.
5.1.2. Метод Лемана.
5.1.3. Отсев делителей.
5.2. Методы Монте-Карло.
5.2.1. Ро-метод Полларда для разложения на множители.
5.2.2. Ро-метод Полларда для вычисления дискретных логарифмов.
5.2.3. Лямбда-метод Полларда для вычисления дискретных логарифмов.
5.3. Детские шаги, гигантские шаги.
5.4. (р — 1)-метод Полларда.
5.5. Метод вычисления значений многочлена.
5.6. Бинарные квадратичные формы.
5.6.1. Основы теории квадратичных форм.
5.6.2. Разложение на множители при помощи представления квадратичными формами.
5.6.3. Композиция и группа классов.
5.6.4. Амбиговы формы и разложение на множители.
5.7. Упражнения.
5.8. Проблемы для исследования.
Глава 6. СУБЭКСПОНЕНЦИАЛЬНЫЕ АЛГОРИТМЫ РАЗЛОЖЕНИЯ НА МНОЖИТЕЛИ.
6.1. Разложение с помощью метода квадратичного решета.
6.1.1. Базовый метод QS.
6.1.2. Базовый алгоритм QS. Резюме.
6.1.3. Быстрые матричные методы.
6.1.4. Вариации больших простых.
6.1.5. Многие полиномы.
6.1.6. Автоматическая инициализация.
6.1.7. Специальное квадратичное решето Жанга.
6.2. Решето числового поля.
6.2.1. Базовый алгоритм NFS: стратегия.
6.2.2. Базовый метод NFS: векторы показателей.
6.2.3. Базовый метод NFS: сложность.
6.2.4. Базовый метод NFS: затруднения.
6.2.5. Базовый метод NFS: квадратные корни.
6.2.6. Базовый метод NFS: итоговый алгоритм.
6.2.7. NFS: дальнейшие соображения.
6.3. Строгое разложение на множители.
6.4. Метод индекс-исчисления для дискретных логарифмов.
6.4.1. Дискретные логарифмы в простых конечных полях.
6.4.2. Вычисление дискретных логарифмов посредством гладких полиномов и гладких целых алгебраических чисел.
6.5. Упражнения.
6.6. Проблемы для исследования.
Глава 7. АРИФМЕТИКА ЭЛЛИПТИЧЕСКИХ КРИВЫХ.
7.1. Основы теории эллиптических кривых.
7.2. Арифметика эллиптических кривых.
7.3 Теоремы Хассе, Дойринга и Ленстры.
7.4. Метод эллиптических кривых.
7.4.1. Базовый алгоритм ЕСМ.
7.4.2. Оптимизации алгоритма ЕСМ.
7.5. Подсчет числа точек на эллиптической кривой.
7.5.1. Метод Шенкса—Местре.
7.5.2. Метод Шуфа.
7.5.3. Метод Аткина—Морейна.
7.6. Доказательство простоты при помощи эллиптических кривых.
7.6.1. Тест на простоту Гольдвассер—Килиана.
7.6.2. Тест на простоту Аткина—Морейна.
7.6.3. Быстрое доказательство простоты при помощи эллиптических кривых (fastECPP).
7.7. Упражнения.
7.8. Проблемы для исследования.
Глава 8. ЭТИ ВЕЗДЕСУЩИЕ ПРОСТЫЕ ЧИСЛА.
8.1. Криптография.
8.1.1. Обмен ключом по Диффи—Хеллману.
8.1.2. Криптосистема RSA.
8.1.3. Криптосистемы на эллиптических кривых (криптосистемы ЕСС).
8.1.4. Протокол подбрасывания монеты.
8.2. Генерирование случайных чисел.
8.2.1. Модулярные методы.
8.3. Методы квази-Монте-Карло.
8.3.1. Теория дискрепанса.
8.3.2. Специальные qMC-последовательности.
8.3.3. Простые числа на Уолл-стрит?.
8.4. Диофантов анализ.
8.5. Квантовые вычисления.
8.5.1. Квантовые машины Тьюринга (QTM) и интуиция.
8.5.2. Квантовый алгоритм факторизации Шора.
8.6. Простые числа в смежных областях, забавные и любопытные факты.
8.7. Упражнения.
8.8. Проблемы для исследования.
Глава 9. БЫСТРЫЕ АЛГОРИТМЫ ДЛЯ РАБОТЫ С БОЛЬШИМИ ЧИСЛАМИ.
9.1. Обзор «школьных» методов.
9.1.1. Умножение.
9.1.2. Возведение в квадрат.
9.1.3. Операции div и mod.
9.2. Усовершенствования в модулярной арифметике.
9.2.1. Метод Монтгомери.
9.2.2. Методы Ньютона.
9.2.3. Модули особого вида.
9.3. Возведение в степень.
9.3.1. Простые двоичные схемы.
9.3.2. Улучшения схем возведения в степень.
9.4. Улучшения для НОД и поиска обратного элемента.
9.4.1. Двоичные алгоритмы для НОД.
9.4.2. Особые алгоритмы обращения.
9.4.3. Рекурсивные алгоритмы для НОД в случае очень больших операндов.
9.5. Умножение больших чисел.
9.5.1. Методы Карацубы и Тоома—Кука.
9.5.2. Алгоритмы вычисления преобразования Фурье.
9.5.3. Теория сверток.
9.5.4. Методы взвешенного дискретного преобразования (ВДП).
9.5.5. Теоретико-числовые преобразования.
9.5.6. Метод Шёнхаге.
9.5.7. Метод Нюссбаумера.
9.5.8. Сложность алгоритмов умножения.
9.5.9. Приложение к китайской теореме об остатках.
9.6. Операции с многочленами.
9.6.1. Умножение многочленов.
9.6.2. Быстрое обращение многочленов и деление с остатком.
9.6.3. Вычисление значений многочлена в наборе точек.
9.7. Упражнения.
9.8. Проблемы для исследования.
Приложение. ПСЕВДОКОД КНИГИ.
Список литературы.
Работы на русском языке.
Список литературы, добавленной при переводе.
Именной указатель.
Предметный указатель.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Простые числа, Криптографические и вычислительные аспекты, Крэндалл Р., Померане К., 2011 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по математике :: математика :: Крэндалл :: Померане