Теоретико-числовые методы в криптографии, Нестеренко А.Ю., 2012

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

Определение 1.6. Натуральное число р > 1 называется простым, если оно не имеет других натуральных, делителей, отличных от 1 и самого себя.
Рассматривая ряд натуральных чисел, мы можем выделить в нем простые числа, а именно,
2. 3, 5, 7. 11. 13. 17. 19. 23, ...

Как мы покажем немного позже, этот ряд бесконечен.
Определение 1.7. Натуральное число п называется составным, если оно имеет делитель, отличный от 1 и n.
Из данного нами определения следует, что для составного числа п всегда найдутся такие натуральные числа а. Ь. что
n = аb и 1 < а < n, 1 < b < n.

Оглавление
Оглавление
Введение
1 Элементарная теория делимости
1.1 Наибольший общий делитель
1.2 Алгоритм Эвклида
1.3 Простые числа
2 Сравнения
2.1 Сравнения первой степени
2.2 Китайская теорема об остатках
2.3 Функция Эйлера
2.4 Первообразные корни
2.4.1 Первообразные корни по модулю простого числа р
2.4.2 Первообразные корни по модулю ра
2.5 Алгебраическое отступление
3 Многочлены
3.1 Элементарные операции
3.2 Алгоритм Эвклида для многочленов
3.3 Основная теорема арифметики для многочленов
3.4 Дифференцирование многочленов
3.5 Решение сравнений по составному модулю
4 Сравнения старших степеней
4.1 Квадратичные вычеты
4.2 Символ Якоби
4.3 Вычисление квадратного корня
4.4 Вероятностный алгоритм вычисления корней многочленов
5 Непрерывные дроби
5.1 Конечные непрерывные дроби
5.2 Понятие подходящей дроби
5.3 Квадратичные иррациональности
5.4 Наилучшие приближения
6 Простые числа
6.1 Вероятностные тесты проверки простоты
6.1.1 Тест Соловея-Штрассена
6.1.2 Тест Миллера-Рабина
6.2 N — 1 методы доказательства простоты
6.3 N + 1 метод доказательства простоты
6.4 Алгоритмы построения простых чисел
6.4.1 Рекурсивный алгоритм построения простых по известному разложению р — 1
6.4.2 Алгоритм построения сильно простого числа
7 Факторизация целых чисел
7.1 Метод пробного деления
7.2 Метод Ферма
7.2.1 Вычисление квадратного корня
7.2.2 Как быстро проверить, что число является полным квадратом
7.3 Метод Лемана
7.4 Метод Полларда-Флойда
7.5 Метод Брента
7.6 р — 1 метод Полларда
7.7 р + 1 метод Вильямса
7.8 Оптимизация алгоритмов Полларда и Вильямса
7.8.1 Разностная схема
7.8.2 Метод согласования
7.8.3 Поиск пар простых чисел
7.8.4 Поиск циклов в последовательностях
7.9 Метод Женга
7.10 Метод Макки
8 Факторизация целых чисел II
8.1 Метод Крайчика
8.2 Метод непрерывных дробей
8.2.1 Первый вариант
8.2.2 Второй вариант
8.2.3 Метод Моррисона и Бриллхарта
8.2.4 Как выбрать множитель k
8.2.5 Как выбрать квадратичную иррациональность
8.2.6 Заключение
8.3 Метод линейного решета
8.4 Метод квадратичного решета
8.4.1 MPQS - метод нескольких многочленов
9 Дискретное логарифмирование
9.1 Метод согласования
9.2 Логарифмирование в подгруппе составного порядка
9.3 Вероятностные методы
9.3.1 Метод Полларда-Флойда
9.3.2 Метод Госпера
9.4 Субэкспоненциальный метод
9.4.1 Идеология Крайчика
9.4.2 Алгоритм Адлемана
9.4.3 Решение систем линейных сравнений
9.4.4 Асимптотическая оценка метода
Литература.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Теоретико-числовые методы в криптографии, Нестеренко А.Ю., 2012 - fileskachat.com, быстрое и бесплатное скачивание.

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


Скачать книгу Теоретико-числовые методы в криптографии, Нестеренко А.Ю., 2012 - pdf - Яндекс.Диск.