Основные алгоритмы в алгебре и теории чисел
Название спецкурса на английском языке
Basic algorithms in algebra and number theory
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра теоретической информатики]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Эффективность и сложность алгоритма от входного параметра.
Принцип разделяй и властвуй.
Модулярные методы. Китайская теорема об остатках.
Быстрое умножение больших чисел. Фильтрованные и градуированные вычисления.
Групповая и бигрупповая алгебра и изоморфизм последних с алгеброй матриц.
Основы криптографии RSA. Максимальный порядок в группе Эйлера.
Тесты на простоту.
Методы доказательства простоты
Экспоненциальные методы фвкторизации
Субэкспоненциальные методы факторизации
Принцип разделяй и властвуй.
Модулярные методы. Китайская теорема об остатках.
Быстрое умножение больших чисел. Фильтрованные и градуированные вычисления.
Групповая и бигрупповая алгебра и изоморфизм последних с алгеброй матриц.
Основы криптографии RSA. Максимальный порядок в группе Эйлера.
Тесты на простоту.
Методы доказательства простоты
Экспоненциальные методы фвкторизации
Субэкспоненциальные методы факторизации
Список источников
Р. Крэндал, К.Померанс. Простые числа. Криптографические и
вычислительные аспекты, Москва, URSS, 2011.
П. Ноден, К. Китте. Алгебраическая алгоритмика, Москва, Мир, 1999.
С. Дасгупта, Х. Пападимитриу, У. Вазирани. Алгоритмы. Москва, Изд-во МЦНМО, 2014.
вычислительные аспекты, Москва, URSS, 2011.
П. Ноден, К. Китте. Алгебраическая алгоритмика, Москва, Мир, 1999.
С. Дасгупта, Х. Пападимитриу, У. Вазирани. Алгоритмы. Москва, Изд-во МЦНМО, 2014.
Дополнительная информация
e-mail для связи: a_rust@bk.ru
День недели
четверг
Время
16:45-18:20
Аудитория
464
Дата первого занятия
Аудитория первого занятия
464
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.