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

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


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


Тематическое содержание курса
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. Доказательство простоты с использованием эллиптических кривых.

Типовые контрольные задания
Перечень учебной литературы