Теория чисел (основной поток) 2022/23 — различия между версиями
Ekononova (обсуждение | вклад) (Новая страница: «== О курсе == === Полезные ссылки === Почта для сдачи домашних заданий Канал в telegram для объ…») |
Mednik (обсуждение | вклад) м (Mednik переименовал страницу Теория чисел (основной поток) в Теория чисел (основной поток) 2022/23 без оставления перенаправления: Для един…) |
||
| (не показано 25 промежуточных версии 3 участников) | |||
| Строка 1: | Строка 1: | ||
== О курсе == | == О курсе == | ||
| − | + | Это курс основ теории чисел, который содержит такие базовые разделы как алгоритм Евклида, цепные дроби, арифметические функции, теория сравнений, квадратичные вычеты, первообразные корни. Параллельно будет происходить знакомство с задачами математической криптографии и простейшими криптографическими протоколами. | |
=== Полезные ссылки === | === Полезные ссылки === | ||
| Строка 15: | Строка 15: | ||
=== Семинары === | === Семинары === | ||
| + | 225 - Устинов Алексей Владимирович | ||
| + | |||
| + | 226 - Устинов Алексей Владимирович | ||
| + | |||
| + | 227 - Герман Олег Николаевич | ||
| + | |||
| + | 228 - Чанга Марис Евгеньевич | ||
| + | |||
| + | 229 - Калмынин Александр Борисович | ||
| + | |||
| + | 2210 - Калмынин Александр Борисович | ||
| + | |||
| + | 2211 - Фроленков Дмитрий Андреевич | ||
| + | |||
| + | 2212 - Радомский Артём Олегович | ||
=== Ассистенты === | === Ассистенты === | ||
| + | |||
| + | 225 - Августёнок Алина Алексеевна | ||
| + | |||
| + | 226 - Агаев Мурад Хаял оглы | ||
| + | |||
| + | 227 - Ахматбеков Адиль Турарович | ||
| + | |||
| + | 228 - Бобков Константин Максимович | ||
| + | |||
| + | 229 - Марченко Мария Максимовна | ||
| + | |||
| + | 2210 - Нестеренко Алиса Вадимовна | ||
| + | |||
| + | 2211 - Новиков Никита Андреевич | ||
| + | |||
| + | 2212 - Кокоева Мария Райбеговна | ||
| Строка 26: | Строка 57: | ||
== Лекции == | == Лекции == | ||
| + | Лекция 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) Протокол Диффи-Хеллмана. Криптосистема Эль-Гамаля. Квадратичные вычеты. Символ Лежандра. Критерий Эйлера и элементарные свойства символа Лежандра. | ||
| − | == | + | == Семинары == |
| + | |||
| + | == Домашние задания == | ||
| + | [https://disk.yandex.ru/i/vEs_bi8Nkxd1AA ДЗ-1] | ||
| + | [https://disk.yandex.ru/i/7G_9qe1FqBNL4Q ДЗ-2] | ||
| + | [https://disk.yandex.ru/i/6AY7w5AJdtIFPw ДЗ-3] | ||
| + | [https://disk.yandex.ru/i/OFxyWclWYvyysw ДЗ-4] | ||
| + | [https://disk.yandex.ru/i/H2G6wyNXPCqrNA ДЗ-5] | ||
| + | [https://disk.yandex.ru/i/7x_CotH8ClLsTA ДЗ-6] | ||
| + | [https://disk.yandex.ru/i/YwgbtK3hO7ahmw ДЗ-7] | ||
| + | [https://disk.yandex.ru/i/9-GiQKV7Mjws6g ДЗ-8] | ||
| + | [https://disk.yandex.ru/i/164zP0YnI-phrA ДЗ-9] | ||
== Контрольная работа == | == Контрольная работа == | ||
| + | Контрольная работа 4 марта (суббота) в 9:30, длительность - 1:20 | ||
| + | Аудитории R201 (240 чел.), R205 (122 чел.), R301 (240 чел.), R304 (192 чел.), R404 (192 чел.), R405 (122 чел.), R503 (112 чел.) | ||
| + | |||
| + | [https://disk.yandex.ru/i/u9zxkP-37spzcg Контрольная - обобщённый модельный вариант] | ||
| + | |||
| + | В контрольную 4 марта войдут 7 задач указанных типов. | ||
| + | |||
| + | Дистанционное участие возможно для тех, у кого есть уважительная причина, подтверждённая учебным офисом (болезнь, дистанционное обучение, участие в важной олимпиаде). | ||
| + | Перед экзаменом преподаватели должны иметь подтверждение из учебного офиса, что у студента есть уважительная причина. | ||
== Экзамен == | == Экзамен == | ||
| + | Экзамен состоится 31 марта | ||
| + | |||
| + | [https://disk.yandex.ru/i/QOV6-RV0hm6QBg Программа курса] | ||
| + | [https://disk.yandex.ru/i/QPgdlY2yWquqMQ Задачи для экзамена - модельный вариант для основного потока] | ||
| + | == Оценка == | ||
| − | = | + | Итог = min(10, Округление(0.25 * ДЗ + 0.25 * КР + 0.5 * Э)), |
| − | + | где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, Э — оценка за экзамен. | |
| + | Округление арифметическое. | ||
| − | === | + | ==Книги== |
| + | ===Основная литература=== | ||
| + | #[http://mmmf.msu.ru/lect/nesterenko/mainnth.pdf Нестеренко Ю. В., Теория чисел] | ||
| + | #[https://www.studmed.ru/akritas-ag-osnovy-kompyuternoy-algebry-s-prilozheniyami_4cf6c2ced74.html Акритас А.Г. Основы компьютерной алгебры с приложениями. 1994] | ||
| + | #[https://uchebnik.mos.ru/system_2/atomic_objects/files/007/640/620/original/alfutova-ustinov-text.pdf Алфутова Н. Б., Устинов А. В. Алгебра и теория чисел. Сборник задач для математических школ. М.: МЦНМО, 2018] | ||
| + | # [https://mahalex.net/151-153/Buchstab.pdf Бухштаб А. А., Теория чисел] | ||
| + | # [https://math.ru/lib/book/djvu/vinogradov.djvu Виноградов И. М., Основы теории чисел.] | ||
| + | #[https://www.studmed.ru/noden-p-kitte-k-algebraicheskaya-algoritmika-s-uprazhneniyami-i-resheniyami-_dc06f6ef316.html Ноден П., Китте К. Алгебраическая алгоритмика] | ||
| + | #[https://doc.lagout.org/network/3_Cryptography/CRC%20Press%20-%20Handbook%20of%20applied%20Cryptography.pdf Menezes A., Oorschot P. van, Vanstone S. Handbook of Applied Cryptography] | ||
| + | ===Дополнительная литература=== | ||
| − | + | # Василенко, О. Н. Теоретико-числовые методы в криптографии МЦНМО, 2003 | |
| + | # Герман, О. Н., Нестеренко, Ю. Теоретико-числовые методы в криптографии 2012 | ||
| + | # Глухов М. М., Круглов И.А., Пичкур А.Б., Черёмушкин А.В. Введение в теоретико-числовые методы криптографии Лань, 2011 | ||
| + | # Кнут, Д. Е. Искусство программирования для ЭВМ. Том 2: Получисленные алгоритмы ``Вильямс'' , М., Санкт-Петербург, Киев, 2000, 724 | ||
| + | # Коблиц Н. Курс теории чисел и криптографии. М.: ТВП, 2001. | ||
| + | # Ноден, П., Китте, К. Алгебраическая алгоритмика. Изд-во Мир, Москва, 1999 | ||
| + | # Ященко, В. В. (Ed.) Введение в криптографию, МЦНМО, Москва, 1999 | ||
| + | # Hoffstein, J.; Pipher, J., Silverman, J. H. An introduction to mathematical cryptography Springer, 2008, | ||
Текущая версия на 20:34, 9 августа 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) Классы вычетов и арифметические операции над ними. Теорема о полной и приведённой системах вычетов. Теорема Эйлера, Малая теорема Ферма. Критерий обратимости вычета по умножению. Теорема Вильсона.
Лекция 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 * Э)), где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, Э — оценка за экзамен. Округление арифметическое.
Книги
Основная литература
- Нестеренко Ю. В., Теория чисел
- Акритас А.Г. Основы компьютерной алгебры с приложениями. 1994
- Алфутова Н. Б., Устинов А. В. Алгебра и теория чисел. Сборник задач для математических школ. М.: МЦНМО, 2018
- Бухштаб А. А., Теория чисел
- Виноградов И. М., Основы теории чисел.
- Ноден П., Китте К. Алгебраическая алгоритмика
- Menezes A., Oorschot P. van, Vanstone S. Handbook of Applied Cryptography
Дополнительная литература
- Василенко, О. Н. Теоретико-числовые методы в криптографии МЦНМО, 2003
- Герман, О. Н., Нестеренко, Ю. Теоретико-числовые методы в криптографии 2012
- Глухов М. М., Круглов И.А., Пичкур А.Б., Черёмушкин А.В. Введение в теоретико-числовые методы криптографии Лань, 2011
- Кнут, Д. Е. Искусство программирования для ЭВМ. Том 2: Получисленные алгоритмы ``Вильямс , М., Санкт-Петербург, Киев, 2000, 724
- Коблиц Н. Курс теории чисел и криптографии. М.: ТВП, 2001.
- Ноден, П., Китте, К. Алгебраическая алгоритмика. Изд-во Мир, Москва, 1999
- Ященко, В. В. (Ed.) Введение в криптографию, МЦНМО, Москва, 1999
- Hoffstein, J.; Pipher, J., Silverman, J. H. An introduction to mathematical cryptography Springer, 2008,
