Алгоритмы в алгебре и теории чисел

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

1. Эффективность алгоритмов. О- большое нотация.
2. Принцип разделяй и властвуй.
3. Сортировка делением пополам и разбиением по значениям.
4. Представление больших чисел и умножение по Карацуба.
5. Преобразование Фурье и быстрый метод умножения.
6. Умножение матриц методом Штрассена.
7. Групповая и бигрупповая алгебра и изоморфизм последних с алгеброй матриц.
8. Алгоритм Евклида и вычисление обратной по модулю другого числа.
9. Понятие равномерности и их влияние на эффективность работы алгоритмов.
10. Основы криптографии RSA.
11. Тесты на простоту Ферма, Эйлера и Рабина-Миллера.
12. Псевдопростые числа Фибоначчи и Люка.
13. Тест Фробениуса.
14. Круговые многочлены и кандидаты на простые числа.
15. Теорема Люка (о простоте и образующей), тест Пепина для чисел Ферма.
16. Доказательство простоты при наличии разложения n-1 до величины не меньше, чем .
17. n+1 тест простоты и тест Люка для чисел Мерсенна.

1. Тест AKS.
2. Факторизация чисел методом квадратов и методом Лемана.
3. Ро- метод Полларда.
4. Детские шаги, гигантские шаги.
5. Число классов и факторизация за О(exp(ln(n)(1+o(1)))).
6. Метод квадратичного решета QS.
7. Метод решета числового поля NFS.
8. Эллиптические кривые, рациональные точки на кривой.
9. Конечность ранга и структура периодической части.
10. Диофантовые уравнения (системы уравнений), приводящие к нахождению рациональных точек на кривой.
11. Задача о совершенном кирпиче.
12. Задача о латинском квадрате, состоящем из квадратов
13. Задача о пяти квадратах со второй разницей, равным 2.
14. Алгоритмы поиска и установления структуры группы точек конечного порядка.
15. Алгоритмы вычисления ранга и базиса образующих.
16. Факторизация с использованием эллиптических кривых.
17. Доказательство простоты с использованием эллиптических кривых.

• Эффективность алгоритмов. О- большое нотация.
• Принцип разделяй и властвуй.
• Сортировка делением пополам и разбиением по значениям.
• Представление больших чисел и умножение по Карацуба.
• Преобразование Фурье и быстрый метод умножения.
• Умножение матриц методом Штрассена.
• Групповая и бигрупповая алгебра и изоморфизм последних с алгеброй матриц.
• Алгоритм Евклида и вычисление обратной по модулю другого числа.
• Понятие равномерности и их влияние на эффективность работы алгоритмов.
• Основы криптографии 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.