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

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

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

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

• Полугруппа, Моноид, Группа
• Гомоморфизм групп, Изоморфизм групп
• Подгруппа
• Порядок элемента группы, циклические группы, конечно порожденные группы, p-группы
• Теорема о подгруппах циклической группы
• Представление конечных групп перестановками (регулярное представление группы)
• Смежные классы, теорема Лагранжа, нормальные подгруппы, факторгруппы
• Гомоморфизмы и нормальные группы

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

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

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

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

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

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

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

• Квадратичные вычеты
• Цепные дроби

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

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

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

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

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

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