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

Версия 16:53, 28 января 2024

О курсе

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

Предварительная программа

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

Дополнительные главы теории чисел (курс в 4-м модуле 2022-2023 у.г.)

Семинары

Преподаватели и учебные ассистенты

Правила выставления оценок

В домашнем задании каждая задача оценивается в 10 баллов. Баллы за задачи суммируются и линейно шкалируются на 10-балльную шкалу без округления. Итоговая оценка за ДЗ получается усреднением оценок по всем ДЗ (без округления). Округление происходит только в конце при вычислении итоговой оценки за курс.

Правила сдачи заданий

Всё должно быть написано аккуратно и понятно.

ПРОСРОЧКА: У Вас есть возможность дважды отправить домашнее задание после истечения срока сдачи в течение 24 часов. Однако этот шанс не может быть использован для сдачи последнего домашнего задания.

Лекции

Лекция 1 (12.01.2023) Основная теорема арифметики. Определение кольца. Сложность алгоритмов. Алгоритм Евклида. Расширенный алгоритм Евклида. Решение уравнения Уравнение ax+by=1 с помощью цепных дробей. [A]

Лекция 2 (19.01.2023) Оценка числа шагов в алгоритме Евклида. Оценка сложности алгоритма Евклида. Общий вид решения уравнения ax+by=c. Мультипликативные функции. Свёртка Дирихле. Формула обращения Мёбиуса. Функция Эйлера. Тождество Гаусса. Формула для функции Эйлера. [AР,Б,ВИМ]

Лекция 3 (25.01.2023, вместо 02.02.2023) Ряды Дирихле. Дзета-функция Римана. Ряды Дирихле для простейших мультипликативных функций. Сравнения и их свойства. Полная и приведённая системы вычетов. Кольцо вычетов. Определение группы. Примеры групп. Группа обратимых элементов кольца вычетов. [Б,ВИМ]

Лекция 4 (26.01.2023) Группа обратимых элементов кольца с единицей. Поле вычетов по простому модулю. Малая теорема Ферма и теорема Эйлера. Псевдопростые числа. Числа Кармайкла. Деление многочленов с остатком. Теорема о числе корней многочлена. Теорема Вильсона.

Лекции предыдущего года

Лекция 1 (12.01.2023) Сложность алгоритмов. Алгоритм Евклида. Теорема Ламе. Расширенный алгоритм Евклида. [A]

Лекция 2 (19.01.2023) Основная теорема арифметики. Уравнение ax+by=c. Цепные дроби. Представление рациональных чисел конечными цепными дробями. Рекуррентные соотношения на числители и знаменатели подходящих дробей. [Б, ВИМ,Х]

Лекция 3 (26.01.2023) Свойства подходящих дробей. Бесконечные цепные дроби. Приближение чисел подходящими дробями. Теорема Лежандра (критерий подходящей дроби).[Б, ВИМ, Х]

Лекция 4 (02.02.2023) Теорема Лежандра (критерий подходящей дроби). Сравнения и их свойства. Полная и приведённая системы вычетов. Функция Эйлера. Теорема Эйлера. Малая теорема Ферма. Псевдопростые числа Ферма.

Лекция 5 (03.02.2023) Тест "Ферма". Числа Кармайкла. Китайская теорема об остатках (два доказательства). Группы, кольца, поля. Кольцо вычетов. Группа обратимых элементов кольца вычетов. [ВЭБ]

Лекция 6 (16.02.2023) Теорема о числе корней многочлена над полем. Теорема Вильсона. Тест сильной псевдопростоты. Изоморфизм групп. Изоморфизм колец. Прямое произведение групп. Прямое произведение колец. Китайская теорема об остатках как изоморфизм колец. Мультипликативность функции Эйлера. Формула для вычисления функции Эйлера. [НК]

(23.02.2023) Лекция пропала из-за праздника.

Лекция 7 (02.03.2023) RSA, шифрование + ЭЦП. Понятие о криптографии с открытым ключом. [MOV] Подгруппы. Теорема Лагранжа о порядке подгруппы. Циклические группы. [ВЭБ]

Лекция 8 (09.03.2023) Следствия теоремы Лагранжа. Первообразные корни (ПК). Критерий ПК. Индексы и их свойства. Криптосистемы Диффи -- Хеллмана и Эль Гамаля. Квадратичные вычеты. Критерий Эйлера.

Лекция 9 (16.03.2023) Символ Лежандра. Простейшие свойства символа Лежандра. Квадратичный закон взаимности. Символ Якоби.

Лекция 10 (17.03.2023) Свойства символа Якоби. Псевдопростые числа Эйлера. Тест Соловея -- Штрассена. Протоколы привязки к биту. Привязка к биту Гольдвассер -- Микали. Шифрование Гольдвассер -- Микали. Криптосистема Гольдвассер -- Микали как криптосистема гомоморфного шифрования.

Видеозаписи

Конспект лекций (будет дорабатываться)

Семинары

Семинар 1, Семинар 2, Семинар 3

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

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

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

Экзамен

Оценка

В течение года установлены следующие формы контроля:

• один письменный экзамен (ЭК), в сессию после модуля;
• одна письменная контрольная работа (KР), которую планируется провести в середине 3-го модуля;
• один коллоквиум (KЛ), который планируется провести в конце 3-го модуля;
• около 10 домашних заданий (ДЗ, где ДЗ --- есть среднее арифметическое оценок всех домашних работ); обычно домашнее задание выдается к каждому семинару.

Накопленная Оценка, НО, вычисляется без округления по следующей формуле: НО = 0.4 * ДЗ + 0.2 * Кр + 0.4 * КЛ. Итоговая Оценка за Курс, ИО, вычисляется по следующей формуле: ИО = Округление(7/10*НО + 3/10*ЭК),

где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, ЭК — оценка за экзамен, КЛ ¬– оценка за коллоквиум. Если НО не меньше 8 (без округления), то студент может не сдавать экзамен. В этом случае ИО = Округление(НО). Округление арифметическое.

Ведомость

Сводная таблица с оценками по ДЗ

Книги

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

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

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

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