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