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

Теоретико-числовые методы в криптографии, Нестеренко А.Ю., 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 Асимптотическая оценка метода
Литература.

Рейтинг:	4.8 баллов / 2537 оценок
Формат:	Книга
Уже скачали:	12733 раз

Отзывы читателей

Ой!

К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Теоретико-числовые методы в криптографии, Нестеренко А.Ю., 2012. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.

Бесплатная библиотека - 1 338 003 изданий в библиотеке

Категории

Книги

Аудиокниги

Журналы

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

Похожие Книги

Полный список населенных мест Уфимской Губернии..

Металлоискатели

Мангазея.

Среднее Поднепровье на рубеже нашей эры.

Основы профессионального бильярда (Видео обучение)

Позвоночник - массаж, упражнения, травы, правильная осанка (2009) DVDRip

Выпуск XLV.Список населенных мест Российской Империи..

Выпуск ХXXVII.Список населенных мест Российской Империи..

Выпуск ХXXVI.Список населенных мест Российской Империи..

Интерфейс RS232. Связь между компьютером и микроконтроллером. От DOS к Windows 98/XP

Вы не зарегистрированы!

Отзывы читателей

Ой!

Бесплатная библиотека - 1 338 003 изданий в библиотеке

Категории

Книги

Аудиокниги

Журналы

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

Похожие Книги

Вы не зарегистрированы!

Отзывы читателей

Ой!

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

Регистрация

Авторизация