Теория чисел (пилотный поток) 2022/23 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Ekononova (обсуждение | вклад) (Новая страница: «== О курсе == left Курс читается для студентов 3-го курса [https://cs.hse.ru/…») |
Mednik (обсуждение | вклад) м (Mednik переименовал страницу Теория чисел (пилотный поток) в Теория чисел (пилотный поток) 2022/23 без оставления перенаправления: Для един…) |
||
| (не показано 85 промежуточных версии 3 участников) | |||
| Строка 1: | Строка 1: | ||
== О курсе == | == О курсе == | ||
| − | + | Это курс основ теории чисел, который содержит такие базовые разделы как алгоритм Евклида, цепные дроби, арифметические функции, теория сравнений, квадратичные вычеты, первообразные корни. Параллельно будет происходить знакомство с задачами математической криптографии и простейшими криптографическими протоколами. | |
| − | + | === Предварительная программа === | |
| − | + | # Алгоритмы и их сложность. Классические алгоритмы целочисленной арифметики. Быстрый алгоритм возведения в степень. | |
| − | + | # Алгоритм Евклида и его варианты. Теорема Ламе. Расширенный алгоритм Евклида. | |
| − | + | # Конечные цепные дроби. Свойства подходящих дробей. | |
| − | + | # Бесконечные цепные дроби. Однозначность представления действительных чисел цепными дробями. Теорема Лагранжа. | |
| − | + | # Теория сравнений. Кольцо вычетов. Группа обратимых кольца вычетов. Теорема Вильсона. Функция Эйлера. Теоремы Ферма и Эйлера. [Простейшие детерминированные и вероятностные тесты на простоту. Псевдопростые, абсолютно псевдопростые и сильно псевдопростые числа. Понятие о криптографии с открытым ключом. Система шифрования RSA. Криптосистема Эль-Гамаля.] | |
| + | # Китайская теорема об остатках. Решение систем линейных сравнений. Решение полиномиальных сравнений. [Криптосистема Рабина и её модификации. ] | ||
| + | # Квадратичные вычеты. Свойства символов Лежандра и Якоби. Квадратичный закон взаимности. [Тест Соловея--Штрассена. Псевдопростые числа Эйлера. Протоколы, использующие свойства символа Якоби. Генератор Блюм -- Блюма -- Шуба. Криптосистема Блюма -- Гольдвассер. Криптосистема Гольдвассер -- Микали.] | ||
| + | # Первообразные корни и индексы. Структура группы $\mathbb{Z}^*_m$ для произвольного $m$ [Метод Диффи-Хеллмана. Дискретное логарифмирование. Протоколы аутентификации и "подбрасывание монеты по телефону". Хеш-функция Шаума -- Хайста -- Пфитсман.] | ||
| + | # Интерполяционный многочлен Лагранжа и его связь с китайской теоремой об остатках. Умножение Карацубы. [Разделение секрета Шамира.] | ||
| + | # Дискретное преобразование Фурье. Быстрое преобразование Фурье. | ||
=== Полезные ссылки === | === Полезные ссылки === | ||
| − | [ | + | [[Дополнительные главы теории чисел]] (курс в 4-м модуле 2022-2023 у.г.) |
| − | + | ||
| − | [ | + | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
=== Семинары === | === Семинары === | ||
| − | + | 221, 222 -- Устинов Алексей Владимирович, | |
| − | + | 223, 224 -- Калмынин Александр Борисович. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
=== Ассистенты === | === Ассистенты === | ||
| − | + | 221 - Свирщевский Юрий, | |
| − | + | 222 - Шевченко Пётр, | |
| − | + | 223 - Кучерявый Пётр, | |
| − | + | 224 - Пичушкин Антон. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
=== Правила выставления оценок === | === Правила выставления оценок === | ||
| − | В | + | В домашнем задании каждая задача оценивается в 10 баллов. Баллы за задачи суммируются и линейно шкалируются на 10-балльную шкалу без округления. |
| − | + | Итоговая оценка за ДЗ получается усреднением оценок по всем ДЗ (без округления). Округление происходит только в конце при вычислении итоговой оценки за курс. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | Итоговая оценка | + | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
=== Правила сдачи заданий === | === Правила сдачи заданий === | ||
| − | + | Всё должно быть написано аккуратно и понятно. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
== Лекции == | == Лекции == | ||
| − | + | Лекция 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) Свойства символа Якоби. Псевдопростые числа Эйлера. Тест Соловея -- Штрассена. Протоколы привязки к биту. Привязка к биту Гольдвассер -- Микали. Шифрование Гольдвассер -- Микали. Криптосистема Гольдвассер -- Микали как криптосистема гомоморфного шифрования. | |
| − | + | [https://disk.yandex.ru/d/hVWLMgTBxXHBUQ/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F%20%D1%87%D0%B8%D1%81%D0%B5%D0%BB%20(%D0%BF%D0%B8%D0%BB%D0%BE%D1%82) Видеозаписи] | |
| − | + | [https://drive.google.com/file/d/1Cj7MMGnnc8sHbaajGIuj_WaU7XJppNeG/view?usp=sharing Конспект лекций] (будет дорабатываться) | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
== Семинары == | == Семинары == | ||
| − | + | [https://drive.google.com/file/d/1xcAMuIxRweXe2OwquLAFet1i_FlGYsoO/view?usp=share_link Семинар 1], | |
| + | [https://drive.google.com/file/d/1JeP_i33HVjYh4xa5f4OTh6k8pmEwbMSW/view?usp=sharing Семинар 2], | ||
| + | [https://drive.google.com/file/d/1si29qrjb8-IwjinOQ9RGZrsah_kuGb1m/view?usp=sharing Семинар 3], | ||
| + | [https://drive.google.com/file/d/1icEzaxof7azcl9TYl2zKLXBzIEVJkLN3/view?usp=sharing Семинар 4], | ||
| + | [https://drive.google.com/file/d/1qACnKnAN_5q8YoTZUALBuzCiguuFM61h/view?usp=sharing Семинар 5], | ||
| + | [https://drive.google.com/file/d/15ixVi9n-0LoJXE-Po17-4A8g0FpFhlrx/view?usp=sharing Семинар 6], | ||
| + | [https://drive.google.com/file/d/1MkS5kSDqtb7kZg1ji5tuvFjz-AFdW8_k/view?usp=sharing Семинар 7], | ||
| + | [https://drive.google.com/file/d/11e7Wsz2EurOXg1tYHDxUQCmnlLp--XBt/view?usp=sharing Семинар 8], | ||
| + | [https://drive.google.com/file/d/11U6uqMNbu6FHG4gGFu-AFM3SsK-Gc7-6/view?usp=sharing Семинар 9], | ||
| + | [https://drive.google.com/file/d/12V3AT7KyJb-UVcnU4kBVrt_bq6eA1xdW/view?usp=sharing Семинар 10] | ||
| − | + | == Домашние задания == | |
| + | [https://drive.google.com/file/d/141IpVFYcQ5kmk37kJDtMfcVZWeEwwTzp/view?usp=share_link ДЗ-1] | ||
| + | [https://drive.google.com/file/d/1brnvq3q4qFuDijbnXhdN4a8rGNG6mSY8/view?usp=sharing ДЗ-2] | ||
| + | [https://drive.google.com/file/d/13hXP1H-wbsXtsnu-ClMKzTTeH57iUgRe/view?usp=sharing ДЗ-3] | ||
| + | [https://drive.google.com/file/d/1B6grzE-KcVaTZSAt1LaCmdCWswqDk4f2/view?usp=sharing ДЗ-4] | ||
| + | [https://drive.google.com/file/d/1qlLxOB7-6wnU_oarM8DTp3lgFocX7pea/view?usp=sharing ДЗ-5] | ||
| + | [https://drive.google.com/file/d/1vt4JST4uWx47G-WNFrtU7G1FKRJmqMvp/view?usp=sharing ДЗ-6] | ||
| + | [https://drive.google.com/file/d/1G4L8qLzHzZhVc0IkLbFFVrjSDAC0pYa9/view?usp=sharing ДЗ-7] | ||
| + | [https://drive.google.com/file/d/17STL86ly4A4ZnlAMsRXeloLfCh_iTsrf/view?usp=sharing ДЗ-8] | ||
| + | [https://drive.google.com/file/d/1cCtCRwj4Q7d6MEt5B1SmOs-Seqf6FqNQ/view?usp=sharing ДЗ-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 задач указанных типов. | |
| − | + | Дистанционное участие возможно для тех, у кого есть уважительная причина, подтверждённая учебным офисом (болезнь, дистанционное обучение, участие в важной олимпиаде). | |
| − | + | Перед экзаменом преподаватели должны иметь подтверждение из учебного офиса, что у студента есть уважительная причина. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
== Экзамен == | == Экзамен == | ||
| + | Экзамен письменный, 2.5 часа. | ||
| + | [https://drive.google.com/file/d/1fC2aFymBJCi9Di9xlNjkdxtxjiGxDgNp/view?usp=sharing Билеты к экзамену (с баллами).] | ||
| + | Модельные задачи в последнем билете. | ||
| − | + | == Оценка == | |
| − | = | + | Итог = min(10, Округление(0.25 * ДЗ + 0.25 * КР + 0.5 * Э)), |
| − | + | где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, Э — оценка за экзамен. | |
| − | + | Округление арифметическое. | |
| − | * | + | |
| − | * | + | |
| − | * | + | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | |||
| − | [[ | + | ==Книги== |
| + | ===Основная литература=== | ||
| + | # [A] [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://mathprofi.com/uploads/files/2581_f_41_e.b.vinberg-kurs-algebry-2-e-izd.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://math.ru/lib/120 Хинчин А. Я., Цепные дроби.] | ||
| + | # [MOV] [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] | ||
| − | + | ===Дополнительная литература=== | |
| − | |||
| − | |||
| − | [[ | + | # [https://techlibrary.ru/b/2j1a1s1j1m1f1o1l1p_2w.2v._3a1f1p1r1f1t1j1l1p-1y1j1s1m1p1c2c1f_1a1m1d1p1r1j1t1n2c_1c_1l1r1j1q1t1p1d1r1a1v1j1j._2003.pdf Василенко, О. Н. Теоретико-числовые методы в криптографии МЦНМО, 2003] |
| + | # Герман, О. Н., Нестеренко, Ю. Теоретико-числовые методы в криптографии 2012 | ||
| + | # Глухов М. М., Круглов И.А., Пичкур А.Б., Черёмушкин А.В. Введение в теоретико-числовые методы криптографии Лань, 2011 | ||
| + | # Кнут, Д. Е. Искусство программирования для ЭВМ. Том 2: Получисленные алгоритмы "Вильямс" , М., Санкт-Петербург, Киев, 2000 | ||
| + | # [http://lib.ysu.am/open_books/416134.pdf Коблиц Н. Курс теории чисел и криптографии. М.: ТВП, 2001.] | ||
| + | # [http://mmmf.msu.ru/lect/nesterenko/mainnth.pdf Нестеренко Ю. В., Теория чисел] | ||
| + | #[https://library.samdu.uz/files/5ef5e9f7c2b02d90200f92776db5bbc3_%D0%92%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2_%D0%BA%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%8E_by_%D0%9F%D0%BE%D0%B4_%D0%BE%D0%B1%D1%89_%D1%80%D0%B5%D0%B4_%D0%AF%D1%89%D0%B5%D0%BD%D0%BA%D0%BE_%D0%92_%D0%92_2012.pdf Ященко, В. В. (ред.) Введение в криптографию, МЦНМО, Москва, 1999] | ||
| + | # Hoffstein, J.; Pipher, J., Silverman, J. H. An introduction to mathematical cryptography Springer, 2008, | ||
Текущая версия на 20:33, 9 августа 2023
Содержание
О курсе
Это курс основ теории чисел, который содержит такие базовые разделы как алгоритм Евклида, цепные дроби, арифметические функции, теория сравнений, квадратичные вычеты, первообразные корни. Параллельно будет происходить знакомство с задачами математической криптографии и простейшими криптографическими протоколами.
Предварительная программа
- Алгоритмы и их сложность. Классические алгоритмы целочисленной арифметики. Быстрый алгоритм возведения в степень.
- Алгоритм Евклида и его варианты. Теорема Ламе. Расширенный алгоритм Евклида.
- Конечные цепные дроби. Свойства подходящих дробей.
- Бесконечные цепные дроби. Однозначность представления действительных чисел цепными дробями. Теорема Лагранжа.
- Теория сравнений. Кольцо вычетов. Группа обратимых кольца вычетов. Теорема Вильсона. Функция Эйлера. Теоремы Ферма и Эйлера. [Простейшие детерминированные и вероятностные тесты на простоту. Псевдопростые, абсолютно псевдопростые и сильно псевдопростые числа. Понятие о криптографии с открытым ключом. Система шифрования RSA. Криптосистема Эль-Гамаля.]
- Китайская теорема об остатках. Решение систем линейных сравнений. Решение полиномиальных сравнений. [Криптосистема Рабина и её модификации. ]
- Квадратичные вычеты. Свойства символов Лежандра и Якоби. Квадратичный закон взаимности. [Тест Соловея--Штрассена. Псевдопростые числа Эйлера. Протоколы, использующие свойства символа Якоби. Генератор Блюм -- Блюма -- Шуба. Криптосистема Блюма -- Гольдвассер. Криптосистема Гольдвассер -- Микали.]
- Первообразные корни и индексы. Структура группы $\mathbb{Z}^*_m$ для произвольного $m$ [Метод Диффи-Хеллмана. Дискретное логарифмирование. Протоколы аутентификации и "подбрасывание монеты по телефону". Хеш-функция Шаума -- Хайста -- Пфитсман.]
- Интерполяционный многочлен Лагранжа и его связь с китайской теоремой об остатках. Умножение Карацубы. [Разделение секрета Шамира.]
- Дискретное преобразование Фурье. Быстрое преобразование Фурье.
Полезные ссылки
Дополнительные главы теории чисел (курс в 4-м модуле 2022-2023 у.г.)
Семинары
221, 222 -- Устинов Алексей Владимирович, 223, 224 -- Калмынин Александр Борисович.
Ассистенты
221 - Свирщевский Юрий, 222 - Шевченко Пётр, 223 - Кучерявый Пётр, 224 - Пичушкин Антон.
Правила выставления оценок
В домашнем задании каждая задача оценивается в 10 баллов. Баллы за задачи суммируются и линейно шкалируются на 10-балльную шкалу без округления. Итоговая оценка за ДЗ получается усреднением оценок по всем ДЗ (без округления). Округление происходит только в конце при вычислении итоговой оценки за курс.
Правила сдачи заданий
Всё должно быть написано аккуратно и понятно.
Лекции
Лекция 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, Семинар 4, Семинар 5, Семинар 6, Семинар 7, Семинар 8, Семинар 9, Семинар 10
Домашние задания
ДЗ-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 задач указанных типов.
Дистанционное участие возможно для тех, у кого есть уважительная причина, подтверждённая учебным офисом (болезнь, дистанционное обучение, участие в важной олимпиаде). Перед экзаменом преподаватели должны иметь подтверждение из учебного офиса, что у студента есть уважительная причина.
Экзамен
Экзамен письменный, 2.5 часа. Билеты к экзамену (с баллами). Модельные задачи в последнем билете.
Оценка
Итог = min(10, Округление(0.25 * ДЗ + 0.25 * КР + 0.5 * Э)), где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, Э — оценка за экзамен. Округление арифметическое.
Книги
Основная литература
- [A] Акритас А.Г. Основы компьютерной алгебры с приложениями. 1994
- [АУ] Алфутова Н. Б., Устинов А. В. Алгебра и теория чисел. Сборник задач для математических школ. М.: МЦНМО, 2018
- [Б] Бухштаб А. А., Теория чисел
- [ВЭБ] Винберг Э. Б. Курс алгебры
- [ВИМ] Виноградов И. М., Основы теории чисел.
- [НК] Ноден П., Китте К. Алгебраическая алгоритмика
- [Х] Хинчин А. Я., Цепные дроби.
- [MOV] Menezes A., Oorschot P. van, Vanstone S. Handbook of Applied Cryptography
Дополнительная литература
- Василенко, О. Н. Теоретико-числовые методы в криптографии МЦНМО, 2003
- Герман, О. Н., Нестеренко, Ю. Теоретико-числовые методы в криптографии 2012
- Глухов М. М., Круглов И.А., Пичкур А.Б., Черёмушкин А.В. Введение в теоретико-числовые методы криптографии Лань, 2011
- Кнут, Д. Е. Искусство программирования для ЭВМ. Том 2: Получисленные алгоритмы "Вильямс" , М., Санкт-Петербург, Киев, 2000
- Коблиц Н. Курс теории чисел и криптографии. М.: ТВП, 2001.
- Нестеренко Ю. В., Теория чисел
- Ященко, В. В. (ред.) Введение в криптографию, МЦНМО, Москва, 1999
- Hoffstein, J.; Pipher, J., Silverman, J. H. An introduction to mathematical cryptography Springer, 2008,
