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

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

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

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

• Системы счисления
• Арифметика чисел в b-ичной системе счисления (Длинная арифметика)
• Разложение на множители (факторизация)

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

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

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

• Решето Эратосфена
• Быстрое возведение в степень
• Умножение по Монтгомери
• Дискретное преобразование Фурье
• Быстрое преобразование Фурье

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

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

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

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

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

• Определение кольца, подкольца, изоморфизмы колец
• Делители нуля, области целостности
• Единицы (обратимые элементы), группа обратимых элементов
• Неразложимые элементы, ассоциированные элементы и разложение на множители в целостных кольцах
• Евклидовы кольца

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

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

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

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

• Теорема о цикличности мультипликативной группы поля [math]\mathbb{Z}/p\mathbb{Z}[/math]
• Первообразные корни
  • Теорема о существовании первообразных корней по модулям вида [math]2,4,p^n,2\cdot p^n[/math]
• Квадратичные вычеты, количество квадратичных вычетов по простому модулю
  • Символ Лежандра, критерий Эйлера
  • Теорема о [math]((\frac{p-1}{2})!)^2\equiv -1 (mod ~p)[/math] при [math]p=4\cdot k+1[/math]
  • Лемма Гаусса для вычисления квадратичного характера числа по простому модулю

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

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

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

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

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

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

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

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

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

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

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

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