====== Алгоритмы в алгебре и теории чисел ======
=== Айдагулов Р.Р. ===

----

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

----

== Тематическое содержание курса ==
== 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.