Учебное пособие. — М.: Московский государственный институт
электроники и математики, 2012. — 224 с. — ISBN 978-5-94506-320-4.
Изложен курс алгоритмической теории чисел с приложениями. Основное
внимание уделено вопросам строгого обоснования, эффективной
реализации и анализа трудоемкости алгоритмов, используемых в
криптографических приложениях. Рассматриваются вопросы решения
некоторых диофантовых уравнений, вопросы решения сравнений
произвольных степеней по простому и составному модулям, а также
методы доказательства простоты и построения больших простых чисел,
методы решения задач дискретного логарифмирования и разложения
больших целых чисел на множители.
Предназначено студентам старших курсов МИЭМ, обучающимся по специальности "Компьютерная безопасность". Введение
Элементарная теория делимости
Наибольший общий делитель
Алгоритм Эвклида
Простые числа
Сравнения
Сравнения первой степени
Китайская теорема об остатках
Функция Эйлера
Алгебраическое отступление
Многочлены
Элементарные операции
Простые числа
Вероятностные тесты проверки простоты
Тест Соловея-Штрассена
Тест Миллера-Рабина
N — 1 методы доказательства простоты
N + 1 метод доказательства простоты
Алгоритмы построения простых чисел
Рекурсивный алгоритм построения простых по известному разложению р — 1
Алгоритм построения сильно простого числа
Факторизация целых чисел
Метод пробного деления
Метод Ферма
Вычисление квадратного корня
Как быстро проверить, что число является полным квадратом
Метод Лемана
Метод Полларда-Флойда
Метод Брента
р — 1 метод Полларда
р + 1 метод Вильямса
Оптимизация алгоритмов Полларда и Вильямса
Разностная схема
Метод согласования
Поиск пар простых чисел
Поиск циклов в последовательностях
Метод Женга
Метод Макки
Факторизация целых чисел II
Метод Крайчика
Метод непрерывных дробей
Первый вариант
Второй вариант
Метод Моррисона и Бриллхарта
Как выбрать множитель k
Как выбрать квадратичную иррациональность
Заключение
Метод линейного решета
Метод квадратичного решета
MPQS - метод нескольких многочленов
Дискретное логарифмирование
Метод согласования
Логарифмирование в подгруппе составного порядка
Вероятностные методы
Метод Полларда-Флойда
Метод Госпера
Субэкспоненциальный метод
Идеология Крайчика
Алгоритм Адлемана
Решение систем линейных сравнений
Асимптотическая оценка метода
Литература.
Предназначено студентам старших курсов МИЭМ, обучающимся по специальности "Компьютерная безопасность". Введение
Элементарная теория делимости
Наибольший общий делитель
Алгоритм Эвклида
Простые числа
Сравнения
Сравнения первой степени
Китайская теорема об остатках
Функция Эйлера
Алгебраическое отступление
Многочлены
Элементарные операции
Простые числа
Вероятностные тесты проверки простоты
Тест Соловея-Штрассена
Тест Миллера-Рабина
N — 1 методы доказательства простоты
N + 1 метод доказательства простоты
Алгоритмы построения простых чисел
Рекурсивный алгоритм построения простых по известному разложению р — 1
Алгоритм построения сильно простого числа
Факторизация целых чисел
Метод пробного деления
Метод Ферма
Вычисление квадратного корня
Как быстро проверить, что число является полным квадратом
Метод Лемана
Метод Полларда-Флойда
Метод Брента
р — 1 метод Полларда
р + 1 метод Вильямса
Оптимизация алгоритмов Полларда и Вильямса
Разностная схема
Метод согласования
Поиск пар простых чисел
Поиск циклов в последовательностях
Метод Женга
Метод Макки
Факторизация целых чисел II
Метод Крайчика
Метод непрерывных дробей
Первый вариант
Второй вариант
Метод Моррисона и Бриллхарта
Как выбрать множитель k
Как выбрать квадратичную иррациональность
Заключение
Метод линейного решета
Метод квадратичного решета
MPQS - метод нескольких многочленов
Дискретное логарифмирование
Метод согласования
Логарифмирование в подгруппе составного порядка
Вероятностные методы
Метод Полларда-Флойда
Метод Госпера
Субэкспоненциальный метод
Идеология Крайчика
Алгоритм Адлемана
Решение систем линейных сравнений
Асимптотическая оценка метода
Литература.