Теория чисел (основной поток) 2022/23

О курсе

Это курс основ теории чисел, который содержит такие базовые разделы как алгоритм Евклида, цепные дроби, арифметические функции, теория сравнений, квадратичные вычеты, первообразные корни. Параллельно будет происходить знакомство с задачами математической криптографии и простейшими криптографическими протоколами.

Полезные ссылки

Почта для сдачи домашних заданий

Канал в telegram для объявлений: Чат в telegram для обсуждений: Ссылка на курс в Anytask:

Семинары

225 - Устинов Алексей Владимирович

226 - Устинов Алексей Владимирович

227 - Герман Олег Николаевич

228 - Чанга Марис Евгеньевич

229 - Калмынин Александр Борисович

2210 - Калмынин Александр Борисович

2211 - Фроленков Дмитрий Андреевич

2212 - Радомский Артём Олегович

Ассистенты

225 - Августёнок Алина Алексеевна

226 - Агаев Мурад Хаял оглы

227 - Ахматбеков Адиль Турарович

228 - Бобков Константин Максимович

229 - Марченко Мария Максимовна

2210 - Нестеренко Алиса Вадимовна

2211 - Новиков Никита Андреевич

2212 - Кокоева Мария Райбеговна

Лекции

Лекция 1 (12.01.2023) Сложность алгоритмов. Алгоритм Евклида. Представление НОД двух чисел в виде их линейной комбинации с целыми коэффициентами.

Лекция 2 (19.01.2023) Простые и составные числа. Основная теорема арифметики. Цепные дроби. Представление рациональных чисел конечными цепными дробями.

Лекция 3 (26.01.2023) Рекуррентные соотношения на числители и знаменатели подходящих дробей. Свойства подходящих дробей.

Лекция 4 (02.02.2023) Завершение доказательства свойств подходящих дробей. Сходимость бесконечной цепной дроби. Сравнения по модулю и их элементарные свойства.

Лекция 5 (03.02.2023) Классы вычетов и арифметические операции над ними. Теорема о полной и приведённой системах вычетов. Теорема Эйлера, Малая теорема Ферма. Критерий обратимости вычета по умножению. Теорема Вильсона.

Лекция 6 (16.02.2023) Китайская теорема об остатках. Группы, кольца, поля: определения, простейшие примеры. Определения изоморфизма групп и изоморфизма колец.

Лекция 7 (02.03.2023) Китайская теорема об остатках как изоморфизм колец. Мультипликативность функции Эйлера. Явная формула для функции Эйлера. Теорема о количестве корней многочлена над полем.

Лекция 8 (09.03.2023) Показатель числа по модулю и порядок элемента группы. Первообразные корни. Критерий первообразного корня. Понятие дискретного логарифма. Криптосистема RSA. Электронная цифровая подпись.

Лекция 9 (16.03.2023) Протокол Диффи-Хеллмана. Криптосистема Эль-Гамаля. Квадратичные вычеты. Символ Лежандра. Критерий Эйлера и элементарные свойства символа Лежандра.

Домашние задания

ДЗ-1 ДЗ-2 ДЗ-3 ДЗ-4 ДЗ-5 ДЗ-6 ДЗ-7 ДЗ-8 ДЗ-9

Контрольная работа

Контрольная работа 4 марта (суббота) в 9:30, длительность - 1:20

Аудитории R201 (240 чел.), R205 (122 чел.), R301 (240 чел.), R304 (192 чел.), R404 (192 чел.), R405 (122 чел.), R503 (112 чел.)

Контрольная - обобщённый модельный вариант

В контрольную 4 марта войдут 7 задач указанных типов.

Дистанционное участие возможно для тех, у кого есть уважительная причина, подтверждённая учебным офисом (болезнь, дистанционное обучение, участие в важной олимпиаде). Перед экзаменом преподаватели должны иметь подтверждение из учебного офиса, что у студента есть уважительная причина.

Экзамен

Экзамен состоится 31 марта

Программа курса

Задачи для экзамена - модельный вариант для основного потока

Оценка

Итог = min(10, Округление(0.25 * ДЗ + 0.25 * КР + 0.5 * Э)), где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, Э — оценка за экзамен. Округление арифметическое.

Книги

Основная литература

1. Нестеренко Ю. В., Теория чисел
2. Акритас А.Г. Основы компьютерной алгебры с приложениями. 1994
3. Алфутова Н. Б., Устинов А. В. Алгебра и теория чисел. Сборник задач для математических школ. М.: МЦНМО, 2018
4. Бухштаб А. А., Теория чисел
5. Виноградов И. М., Основы теории чисел.
6. Ноден П., Китте К. Алгебраическая алгоритмика
7. Menezes A., Oorschot P. van, Vanstone S. Handbook of Applied Cryptography

Дополнительная литература

1. Василенко, О. Н. Теоретико-числовые методы в криптографии МЦНМО, 2003
2. Герман, О. Н., Нестеренко, Ю. Теоретико-числовые методы в криптографии 2012
3. Глухов М. М., Круглов И.А., Пичкур А.Б., Черёмушкин А.В. Введение в теоретико-числовые методы криптографии Лань, 2011
4. Кнут, Д. Е. Искусство программирования для ЭВМ. Том 2: Получисленные алгоритмы ``Вильямс , М., Санкт-Петербург, Киев, 2000, 724
5. Коблиц Н. Курс теории чисел и криптографии. М.: ТВП, 2001.
6. Ноден, П., Китте, К. Алгебраическая алгоритмика. Изд-во Мир, Москва, 1999
7. Ященко, В. В. (Ed.) Введение в криптографию, МЦНМО, Москва, 1999
8. Hoffstein, J.; Pipher, J., Silverman, J. H. An introduction to mathematical cryptography Springer, 2008,