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

Айдагулов Р.Р.


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


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

2 семестр
Эллиптические кривые в теории чисел и в алгоритмах
  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.