Теория чисел (основной поток) 2022/23 — различия между версиями

Версия 13:13, 3 февраля 2023

О курсе

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

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

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

Канал в 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) Классы вычетов и арифметические операции над ними. Теорема о полной и приведённой системах вычетов. Теорема Эйлера, Малая теорема Ферма. Критерий обратимости вычета по умножению. Теорема Вильсона.

Семинары

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

ДЗ-1 ДЗ-2 ДЗ-3 ДЗ-4

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

Будет проведена одна контрольная работа (ориентировочно) после 6-го занятия.

Экзамен

Оценка

Итог = 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,