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

Лекция - Классы чисел и основная теорема арифметики

• Классы чисел
• Натуральные и целые числа
• Простые числа
• Наибольший общий делитель
• Основная теорема арифметики
• Теоремы о простых числах

Практика - Разложение на множители и длинная арифметика

Лекция - Основные элементы теории чисел

• Сравнения
  • Сравнение чисел по модулю, арифметика по модулю
  • Полная и приведенная система вычетов
  • Отсутствие делителей нуля в приведенной системе вычетов
  • Решение линейных сравнений по модулю, деление остатков
  • Китайская теорема об остатках
  • Малая теорема Ферма
  • Теорема Вильсона
• Теоретико-числовые функции
  • Функция Эйлера
  • Теорема Эйлера
  • Число делителей, сумма делителей, функция Мёбиуса
  • Свертка Дирихле мультипликативных функций

Практика - Основные алгоритмы теории чисел

Лекция - Основы теории групп

• Полугруппа, моноид, группа
• Абелева группа, Конечная группа
• Гомоморфизм групп, изоморфизм групп
• Подгруппа, нормальная подгруппа
• Порядок элемента группы, циклическая группа, конечно порожденная группа
• Теорема о подгруппах циклической группы
• Смежные классы, теорема Лагранжа, факторгруппы

Практика - Основы теории групп

• Вычисление порядка элемента в группе
• Вычисление порядка перестановки в группе перестановок
• Дискретное логарифмирование в группе
• Действие группы на множестве
• Лемма Бернсайда, задача о числе ожерелий
• Представление групп

Лекция - Основы теории колец

Практика - Арифметика полиномов от одной переменной над полем

Лекция - Основы теории полей

• Определение поля и подполя, изоморфизмы полей
• Примеры полей
• Мультипликативная группа поля
• Характеристика поля, простые поля, классификация простых полей
• Поле как линейное пространство над своим подполем
• Расширения полей
• Поле частных кольца, поле Q как поле частных кольца Z

Лекция - Первообразные корни и квадратичные вычеты

• Теорема о цикличности мультипликативной группы поля [math]\mathbb{Z}/p\mathbb{Z}[/math]
• Первообразные корни
• Квадратичные вычеты

Практика - Первообразные корни и квадратичные вычеты

Лекция - Квадратичные вычеты

• Квадратичный закон взаимности
• Символ Якоби и его свойства
• Обобщенный квадратичный закон взаимности
• Алгоритм вычисления символа Якоби

Практика - Вероятностные тесты чисел на простоту

• Тест Ферма проверки чисел на простоту, числа Кармайкла
• Тест Соловея-Штрассена
• Тест Миллера-Рабина

Лекция - Аналитическая теория чисел

• Факты из математического анализа
• Теорема Чебышёва
• Постулат Бертрана
• Уточнение констант в теореме Чебышёва
• Сумма обратных к простым
• Асимптотический закон распределения простых чисел

Практика - Вычисление [math]\pi(x)[/math]

Лекция - Цепные (непрерывные) дроби и уравнение Пелля

• Цепная дробь
  • Связь цепных дробей и алгоритма Евклида
  • Сходимость цепных дробей
  • Цепные дроби как приближение к числу
  • Квадратичная иррациональность
  • Периодичность цепных дробей
  • Цепные дроби для [math]\sqrt{d}[/math] и квадратичных иррациональностей
• Уравнение Пелля
• Представление простых в виде суммы двух квадратов

Лекция - Конечные поля

Практика - Методы разложения полиномов на множители над конечными полями