Алгоритмы в алгебре и теории чисел
Айдагулов Р.Р.
Аннотация курса: В первой части курса включены основные методы построения эффективных алгоритмов, использующие принципы «разделяй и властвуй», быстрое преобразование Фурье. Рассмотрены тесты на простоту, как вероятностные, так и доказывающие простоту (алгоритм АКС). В курс включены также алгоритмы факторизации – как экспоненциальные, так и субэкспоненциальные – квадратичного решета и решета числового поля. Во второй части изучается теория эллиптических кривых как в применении к диофантовым задачам, так и к задачам доказательства простоты и факторизации. Рассматриваются соответствующие им алгоритмы вычисления ранга и образующих и в приложениях к криптографии.
Тематическое содержание курса
1 семестр
Основные алгоритмы в алгебре и теории чисел
- Эффективность алгоритмов. О- большое нотация.
- Принцип разделяй и властвуй.
- Сортировка делением пополам и разбиением по значениям.
- Представление больших чисел и умножение по Карацуба.
- Преобразование Фурье и быстрый метод умножения.
- Умножение матриц методом Штрассена.
- Групповая и бигрупповая алгебра и изоморфизм последних с алгеброй матриц.
- Алгоритм Евклида и вычисление обратной по модулю другого числа.
- Понятие равномерности и их влияние на эффективность работы алгоритмов.
- Основы криптографии RSA.
- Тесты на простоту Ферма, Эйлера и Рабина-Миллера.
- Псевдопростые числа Фибоначчи и Люка.
- Тест Фробениуса.
- Круговые многочлены и кандидаты на простые числа.
- Теорема Люка (о простоте и образующей), тест Пепина для чисел Ферма.
- Доказательство простоты при наличии разложения n-1 до величины не меньше, чем .
- n+1 тест простоты и тест Люка для чисел Мерсенна.
2 семестр
Эллиптические кривые в теории чисел и в алгоритмах
- Тест AKS.
- Факторизация чисел методом квадратов и методом Лемана.
- Ро- метод Полларда.
- Детские шаги, гигантские шаги.
- Число классов и факторизация за О(exp(ln(n)(1+o(1)))).
- Метод квадратичного решета QS.
- Метод решета числового поля NFS.
- Эллиптические кривые, рациональные точки на кривой.
- Конечность ранга и структура периодической части.
- Диофантовые уравнения (системы уравнений), приводящие к нахождению рациональных точек на кривой.
- Задача о совершенном кирпиче.
- Задача о латинском квадрате, состоящем из квадратов
- Задача о пяти квадратах со второй разницей, равным 2.
- Алгоритмы поиска и установления структуры группы точек конечного порядка.
- Алгоритмы вычисления ранга и базиса образующих.
- Факторизация с использованием эллиптических кривых.
- Доказательство простоты с использованием эллиптических кривых.
Типовые контрольные задания
- Эффективность алгоритмов. О- большое нотация.
- Принцип разделяй и властвуй.
- Сортировка делением пополам и разбиением по значениям.
- Представление больших чисел и умножение по Карацуба.
- Преобразование Фурье и быстрый метод умножения.
- Умножение матриц методом Штрассена.
- Групповая и бигрупповая алгебра и изоморфизм последних с алгеброй матриц.
- Алгоритм Евклида и вычисление обратной по модулю другого числа.
- Понятие равномерности и их влияние на эффективность работы алгоритмов.
- Основы криптографии RSA.
- Тесты на простоту Ферма, Эйлера и Рабина-Миллера.
- Псевдопростые числа Фибоначчи и Люка.
- Тест Фробениуса.
- Круговые многочлены и кандидаты на простые числа.
- Теорема Люка (о простоте и образующей), тест Пепина для чисел Ферма.
- Доказательство простоты при наличии разложения n-1 до величины не меньше, чем .
- n+1 тест простоты и тест Люка для чисел Мерсенна.
- Тест AKS.
- Факторизация чисел методом квадратов и методом Лемана.
- Ро-метод Полларда.
- Детские шаги, гигантские шаги.
- Число классов и факторизация за О(exp(ln(n)(1+o(1)))).
- Метод квадратичного решета QS.
- Метод решета числового поля NFS.
- Эллиптические кривые, рациональные точки на кривой.
- Конечность ранга и структура периодической части.
- Диофантовые уравнения (системы уравнений), приводящие к нахождению рациональных точек на кривой.
- Задача о совершенном кирпиче.
- Задача о латинском квадрате, состоящем из квадратов.
- Задача о пяти квадратах со второй разницей, равным 2.
- Алгоритмы поиска и установления структуры группы точек конечного порядка.
- Алгоритмы вычисления ранга и базиса образующих.
- Факторизация с использованием эллиптических кривых.
- Доказательство простоты с использованием эллиптических кривых.
Перечень учебной литературы
- Р. Крендал, К. Померанс. Простые числа. Криптографические и вычислительные аспекты.
- HenryCohen/ HandbookofEllipticandHyperellipticcurveCryptography.
- В.И.Игошин «Теория алгоритмов». 2013.
- Дж. Прескилл «Квантовая информация и квантовые вычисления. Том 1». 2008.
- Под ред. В.В.Ященко «Ведение в криптографию», 2000.
- Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков «Численные методы». 1987.
- О.Н.Василенко «Теоретико-числовые алгоритмы в криптографии», 2006.
- М.П.Минеев, В.Н.Чубариков, «Лекции по арифметическим вопросам криптографии», 2014
- В.И.Крупский, В.Е.Плиско «Математическая логика и теория алгоритмов». 2013.
- Н.П.Редькин «Дискретная математика», 2009.
- Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, “Handbook of Applied Cryptography”, 2014.
- Myasnikov A., Shpilrain V., Ushakov A., “Group-based Cryptography”, 2008.