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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Новая страница: «== О курсе == Это курс основ теории чисел, который содержит такие базовые разделы как алго…»)
 
 
(не показана одна промежуточная версия 3 участников)
Строка 1: Строка 1:
 
== О курсе ==
 
== О курсе ==
  
−
Это курс основ теории чисел, который содержит такие базовые разделы как алгоритм Евклида, цепные дроби, арифметические функции, теория сравнений, квадратичные вычеты, первообразные корни. Параллельно будет происходить знакомство с задачами математической криптографии и простейшими криптографическими протоколами.
+
Это курс основ теории чисел, специализированный для студентов, изучающих компьютерные науки. Параллельно со стандартными понятиями и теоремами из элементарной теории чисел мы будем знакомиться с их приложениями в криптографии и алгоритмической теории чисел.  
−
 
+
−
=== Полезные ссылки ===
+
−
 
+
−
[[Дополнительные главы теории чисел]] (курс в 4-м модуле 2022-2023 у.г.)
+
  
 
=== Преподаватели и учебные ассистенты ===
 
=== Преподаватели и учебные ассистенты ===
 
{| class="wikitable" style="text-align:center"
 
{| class="wikitable" style="text-align:center"
 
|-
 
|-
−
! Группа !! [https://t.me/+DPqKSR-NvsNjM2Zi БПМИ231] !! [https://t.me/+dXJo7lKgKBMyNmRi БПМИ232] !! [https://t.me/+mPvu8F9mMvYwOTZi БПМИ233] !! [https://t.me/+7zMWJlcvMkpjZWNi БПМИ234]
+
! Группа !! [https://t.me/+Y3JXjxaa2tthOTRi БПМИ241] !! [https://t.me/+9HYhouc-imI2YTJi БПМИ242] !! [https://t.me/+LRb47vV9ifs2MDhi БПМИ243 ] !! [https://t.me/+FycnFv5tLMRjODAy БПМИ244] !! [https://t.me/+T-TX2kUZ6BU1YmYy БПМИ245 ]
 
|-
 
|-
−
|| Лектор ||colspan="4"| [https://t.me/AlexeyVUstinov А.В. Устинов]
+
|| Лектор ||colspan="5"| [https://t.me/AlexeyVUstinov А.В. Устинов]
 
|-  
 
|-  
−
|| Семинарист || [https://t.me/AlexeyVUstinov А.В. Устинов] ||colspan="2" | А. Калмынин || Ф. Ожегов
+
|| Семинарист || Ожегов Фёдор Юрьевич || [https://t.me/AlexeyVUstinov А.В. Устинов] ||colspan="2" | А. Калмынин || Бельдиев Иван Сергеевич
 
|-
 
|-
−
|| Ассистент || [https://t.me/TigodanAC Окунев Данила] || [https://t.me/oleja_shpep Рябов Олег] || [https://t.me/andreyvoyko04 Войко Андрей] || [https://t.me/raspberru Грецкая Вера]
+
|| Ассистент || [https://t.me/wa731 Заварин Александр Сергеевич ] || [https://t.me/jtqjd0 Лейла Мурсманидзе] || [https://t.me/lizgbet  Горбач Елизавета Леонидовн] || [https://t.me/wa731 Заварин Александр Сергеевич ] || [https://t.me/raspberru Грецкая Вера Ильинична]
 
|-
 
|-
−
|| Ассистент лектора || colspan="4" | [https://t.me/citizen_murad Агаев Мурад]  
+
|| Ассистент лектора || colspan="5" | [https://t.me/citizen_murad Агаев Мурад]  
 
|-
 
|-
 
|}
 
|}
  
−
=== Правила выставления оценок ===
+
== Лекции ==
  
−
В домашнем задании каждая задача оценивается в 10 баллов. Баллы за задачи суммируются и линейно шкалируются на 10-балльную шкалу без округления.
+
[https://drive.google.com/file/d/13DtZf1COOZu0ndryxoW6zKi7VXuN1D6L/view?usp=sharing Конспект лекций.]
−
Итоговая оценка за ДЗ получается усреднением оценок по всем ДЗ (без округления). Округление происходит только в конце при вычислении итоговой оценки за курс.
+
  
−
=== Правила сдачи заданий ===
+
Лекция 1 (10.01.2025) Основная теорема арифметики. Сравнения и их свойства. Полная и приведённая системы вычетов. Определение группы. Примеры групп. Определение кольца. Примеры колец. Кольцо вычетов. Группа обратимых элементов кольца вычетов. Малая теорема Ферма и теорема Эйлера. Теорема Вильсона.
  
−
Всё должно быть написано аккуратно и понятно.
+
Лекция 2 (17.01.2025) Мультипликативные функции. Мультипликативность функции Эйлера. Тест "Ферма". Псевдопростые числа Ферма. Числа Кармайкла. Тест сильной псевдопростоты. Теорема Рабина (без доказательства). Криптосистема RSA. Электронная подпись RSA.
  
−
ПРОСРОЧКА: У Вас есть возможность дважды отправить домашнее задание после истечения срока сдачи в течение 24 часов. Однако этот шанс не может быть использован для сдачи последнего домашнего задания.
+
Лекция 3 (24.01.2025) Асимметричная криптография. Гомоморфное шифрование. Слепая подпись RSA. Забывчивая передача RSA. Китайская теорема об остатках (КТО), три доказательства. Изоморфизмы групп и колец. Прямое произведение групп и колец. КТО как изоморфизм колец вычетов.
  
−
== Лекции ==
+
Лекция 4 (31.01.2025) Делители нуля. Деление многочленов с остатком. Теорема Безу. Теорема о числе корней многочлена над полем. Расширенный алгоритм Евклида для многочленов. НОД многочленов. Однозначность разложения многочлена в произведение неприводимых. КТО для многочленов. Связь с интерполяционным многочленом Лагранжа. Циклические группы.
  
−
[https://drive.google.com/file/d/1gSAJGCRom_DFr2rho0uzVLtPpVE8NTOi/view?usp=sharing Конспект лекций прошлого года.]
+
Лекция 5 (07.02.2025) Первообразные корни (ПК). Критерий ПК. Существование ПК по простому модулю. Существование ПК по модулю p^2. Существование ПК по модулю p^a.
 +
Существование ПК по модулю 2p^a.
  
−
Лекция 1 (12.01.2024) Основная теорема арифметики. Определение кольца. Сложность алгоритмов. Алгоритм Евклида. Расширенный алгоритм Евклида. Решение уравнения Уравнение ax+by=1 с помощью цепных дробей. [A]
+
Лекция 6 (13.02.2025, вместо 14.02.2025) Индексы. Задача дискретного логарифмирования. Протокол Диффи --  Хеллмана. Вычислительная задача Диффи --  Хеллмана. Протокол Эль-Гамаля. Полиномиально сводимые и вычислительно эквивалентные функции. Вычислительная эквивалентность задач DH и EG. Трёхэтапный протокол Шамира. Квадратичные вычеты. Критерий Эйлера. Символ Лежандра. Простейшие свойства символа Лежандра. Критерий Гаусса.
  
−
Лекция 2 (19.01.2024) Оценка числа шагов в алгоритме Евклида. Оценка сложности алгоритма Евклида. Общий вид решения уравнения ax+by=c. Мультипликативные функции. Свёртка Дирихле. Формула обращения Мёбиуса. Функция Эйлера. Тождество Гаусса. Формула для функции Эйлера. [AР,Б,ВИМ]
+
Лекция 7 (21.02.2025) Квадратичный закон взаимности. Символ Якоби и его свойства. Теорема Лагранжа о порядке подгруппы (без доказательства).  
 +
Тест Соловея -- Штрассена. Оценка числа оснований, для которых тест Соловея -- Штрассена не срабатывает. Псевдопростые числа Эйлера.
  
−
Лекция 3 (25.01.2024, вместо 02.02.2024) Ряды Дирихле. Дзета-функция Римана. Ряды Дирихле для простейших мультипликативных функций. Сравнения и их свойства. Полная и приведённая системы вычетов. Кольцо вычетов. Определение группы. Примеры групп. Группа обратимых элементов кольца вычетов. [Б,ВИМ]
+
Лекция 8 (28.02.2025) Извлечение квадратного корня по модулю простого числа p=4k+3. Числа Блюма. Криптосистема Рабина, шифрование и электронная подпись. Эквивалентность задач факторизации числа Блюма n и извлечения квадратного корня по модулю n. Забывчивая передача Рабина. Протоколы привязки к биту и подбрасывания монеты по телефону. Подбрасывания монеты по телефону с помощью чисел Блюма. Криптосистема Гольдвассер -- Микали: протоколы привязки к биту и шифрования. Гомоморфность криптосистем RSA, Рабина, Эль-Гамаля и Гольдвассер -- Микали.
  
−
Лекция 4 (26.01.2024) Группа обратимых элементов кольца с единицей. Поле вычетов по простому модулю. Малая теорема Ферма и теорема Эйлера. Псевдопростые числа. Числа Кармайкла. Деление многочленов с остатком. Теорема о числе корней многочлена. Теорема Вильсона.
+
Лекция 9 (07.03.2025) Генератор Блюм -- Блюма -- Шуба. Вероятностное шифрование Блюма -- Гольдвассер. Лемма Гензеля. Подъём решений полиномиальных сравнений.
  
−
Лекция 5 (09.02.2024) Тест сильной псевдопростоты. Сильно псевдопростые числа. Китайская теорема об остатках (три доказательства). Изоморфизм групп. Изоморфизм колец. Криптосистема RSA. Электронная подпись RSA.
+
Лекция 10 (14.03.2025) Вероятностное шифрование. Криптосистема Пэйе.
  
−
Лекция 6 (16.02.2024) Подгруппы. Циклические группы. Порядок группы и порядок элемента. Теорема Лагранжа (без доказательства). Первообразные корни (ПК). Критерий ПК. Усиленная теорема Эйлера и её следствие. Теорема о существовании ПК по модулю простого числа.
+
== Семинары и домашние задания ==
 +
[https://drive.google.com/file/d/1ZSTcHS9CqbJq2AzAA6y91PjDc0zkGAG8/view?usp=sharing Семинар + ДЗ 1],
 +
[https://drive.google.com/file/d/1q2Ou3zGrgi_Id-aPNXwTYDzYFAYK35ql/view?usp=sharing Семинар + ДЗ 2],
 +
[https://drive.google.com/file/d/1elYhruCK7xtpyTtxl41PIwRhWQLoMibG/view?usp=sharing Семинар + ДЗ 3],
 +
[https://drive.google.com/file/d/1RZUZMOnbN-CprQxwRCLQTAXN56nLZJg7/view?usp=sharing Семинар + ДЗ 4],
 +
[https://drive.google.com/file/d/1Nuu-4BWhzJjsEyXmrjZauYdZKnRL-5t4/view?usp=sharing Семинар + ДЗ 5],
 +
[https://drive.google.com/file/d/1YbT40MtmAoRE3Ub8V9nDUNTsMJNPP8Nz/view?usp=sharing Семинар + ДЗ 6],
 +
[https://drive.google.com/file/d/12FazuYAB6SxqhRuMlbhRzKs0BKpNgvmv/view?usp=sharing Семинар + ДЗ 7],
 +
[https://drive.google.com/file/d/1YfKU6WvF9gB_B5SEEhYIgIT_sf5-IkME/view?usp=sharing Семинар + ДЗ 8],
 +
[https://drive.google.com/file/d/1LzspFMeyoFhL-e4r7d7ysPKXSs0AWyZr/view?usp=sharing Семинар + ДЗ 9],
 +
[https://drive.google.com/file/d/1fOncLdQfIiZH9m9UlgKrdsC13nQ6r5pM/view?usp=sharing Семинар 10]
  
−
Лекция 7 (22.02.2024, вместо 23.02.2024) ПК по модулям p^2, p^a, 2p^a. Индексы и их свойства. Задача дискретного логарифмирования. Односторонние функции. Протокол Диффи -- Хеллмана. Вычислительная задача Диффи -- Хеллмана DH. Схема шифрования Эль Гамаля. Задача вскрытия схемы шифрования Эль Гамаля EG. Протокол Мэсси -- Омуры. Полиномиально сводимые и полиномиально эквивалентные функции. Полиномиальная эквивалентность функций DH и EG.
+
[https://drive.google.com/file/d/1M8WTigV8mbamxMNg9H0eHlRF6Zdh84IL/view?usp=sharing ДЗ 10 (на каникулы)]
  
−
Лекция 8 (29.02.2024) Квадратичные вычеты. Символ Лежандра и его свойства. Квадратичный закон взаимности. Символ Якоби и его свойства.
 
  
−
Лекция 9 (07.03.2024, вместо 08.03.2024) Тест Соловея -- Штрассена. Псевдопростые числа Эйлера. Оценка числа псевдопростых чисел Эйлера. Тест Миллера -- Рабина (тест сильной псевдопростоты). Теорема Рабина (без доказательства). Связь между разными типами псевдопростых чисел (без доказательства). Протоколы привязки к биту. Привязка к биту Гольдвассер -- Микали.
+
=== Правила выставления оценок ===
  
−
Лекция 10 (15.03.2024) Шифрование Гольдвассер -- Микали. Псевдослучайный генератор Блюм -- Блюма -- Шуба. Вероятностное шифрование Блюма -- Гольдвассер. Криптосистема Рабина, шифрование и электронная подпись. Подбрасывание монетки с помощью криптосистемы Рабина. Забывчивая передача Рабина. Гомоморфное шифрование, примеры (RSA, EG, Рабин, Гольдвассер -- Микали).
+
В домашнем задании каждая задача оценивается в 10 баллов. Баллы за задачи суммируются и линейно шкалируются на 10-балльную шкалу без округления.
 +
Итоговая оценка за ДЗ получается усреднением оценок по всем ДЗ (без округления). Округление происходит только в конце при вычислении итоговой оценки за курс.
  
−
== Семинары ==
+
=== Правила сдачи заданий ===
−
[https://drive.google.com/file/d/1W3rmNbAIA9keq-CpPCbfzprtx20ucwod/view?usp=sharing Семинар 1]
+
−
[https://drive.google.com/file/d/1mCwUMderXKTTRjNvYaGTxka0q_N7OF-d/view?usp=sharing Семинар 2]
+
−
[https://drive.google.com/file/d/11Zf1FgdW5ShCbiecZjXbLJfNvAg0bXJc/view?usp=sharing Семинар 3]
+
−
[https://drive.google.com/file/d/1SKltrMSKEOIPku-3kFnZXIrsIuP6osv4/view?usp=sharing Семинар 4]
+
−
[https://drive.google.com/file/d/1m8pVTW21YU8yTf2iBfhc7NFlB3vDfUeZ/view?usp=sharing Семинар 5]
+
−
[https://drive.google.com/file/d/1C4O6EC1XeL94J5TcFYjaqgXJNWJXXtlv/view?usp=sharing Семинар 6]
+
−
[https://drive.google.com/file/d/1m17206JOrKK8Zs7TAGYyZHAPfL44oQ4X/view?usp=sharing Семинар 7]
+
−
[https://drive.google.com/file/d/1TQBX-p0BwKpz21GT_rJULfo6bUCGZpV3/view?usp=sharing Семинар 8]
+
−
[https://drive.google.com/file/d/1woRlFLeqKkdwj00pNYPdNeFvndaE3uY5/view?usp=sharing Семинар 9]
+
−
[https://drive.google.com/file/d/1ozA8yd5xNb7Tb45tfCOPfdkIo2JgHj0J/view?usp=sharing Семинар 10] <!--  -->
+
  
−
== Домашние задания ==
+
Всё должно быть написано аккуратно и понятно. Ассистент имеет право вызвать студента на защиту задания, если решение неясное или есть подозрение на списывание или использование ИИ. В случае неявки или невозможности объяснить решение студент получает 0 баллов.
  
−
[https://drive.google.com/file/d/13O9GqK97cgGD98Ryqh6MCu9LUCYqNEEN/view?usp=sharing ДЗ-1] [https://drive.google.com/file/d/1SaQ9qDKFNeI_Dw9-8xbG5_Bq6nXZuSP7/view?usp=sharing ДЗ-2] [https://drive.google.com/file/d/1jKSFCyTIY9wBifMIOwmVoRfkPXk52lAm/view?usp=sharing ДЗ-3] [https://drive.google.com/file/d/1zaYvI3jg5JucpAY7h9N1Iq0W5NZiBlK1/view?usp=sharing ДЗ-4] [https://drive.google.com/file/d/1yjOh7-LdhHyYC7B-_uSjWCeS2pN9gl47/view?usp=sharing ДЗ-5]
+
ПРОСРОЧКА: У Вас есть возможность дважды отправить домашнее задание после истечения срока сдачи в течение 24 часов. Однако этот шанс не может быть использован для сдачи последнего домашнего задания.
−
[https://drive.google.com/file/d/1hxfHOpiQoMwvFwyEhC37s5z2w3tpXix8/view?usp=sharing ДЗ-6]
+
−
[https://drive.google.com/file/d/1vuVDI5yz7aD-s1v_98QpQAm-blcC8GeG/view?usp=sharing ДЗ-7]
+
−
[https://drive.google.com/file/d/1L0lWnVI5zbBjVZdWDMFsc3g1vvkWO0IB/view?usp=sharing ДЗ-8]
+
−
[https://drive.google.com/file/d/1XZ21Ony4UqtWdJS_HYxTRc7sRLl5Wfaf/view?usp=sharing ДЗ-9] <!-- -->
+
  
 
== Контрольная работа ==
 
== Контрольная работа ==
  
−
Контрольная работа 2 марта (суббота) в 11:10, длительность - 1:30.  
+
21 февраля 18:10-19:30.
  
−
==== Распределение по аудиториям ====
+
Распределение по аудиториям R201 (241, 242, 243) и R204 (244, 245).
−
R401 - БПМИ231, БПМИ234
+
  
−
R404 - БПМИ232, БПМИ233
+
Темы: теоремы Ферма, Эйлера, Вильсона; псевдопростые числа; числа Кармайкла; китайская теорема об остатках для чисел и многочленов; первобразные корни и индексы.
  
−
[https://drive.google.com/file/d/1T_llw5UMgtlIauw3uPtFONwwBpdPb8Yk/view?usp=sharing Модельный вариант]
+
[https://drive.google.com/file/d/1pUBEbmrBlFE81Qt3Gtzdf7DKqflG0BZL/view?usp=sharing Демо-вариант]
  
 
Дистанционное участие возможно для тех, у кого есть уважительная причина, подтверждённая учебным офисом (болезнь, дистанционное обучение, участие в важной олимпиаде).  
 
Дистанционное участие возможно для тех, у кого есть уважительная причина, подтверждённая учебным офисом (болезнь, дистанционное обучение, участие в важной олимпиаде).  
 
Перед экзаменом преподаватели должны иметь подтверждение из учебного офиса, что у студента есть уважительная причина.
 
Перед экзаменом преподаватели должны иметь подтверждение из учебного офиса, что у студента есть уважительная причина.
  
−
[https://us06web.zoom.us/j/81522212645?pwd=mlNMksCHuzArr8v062S5BJluRGRolJ.1 Ссылка] для тех, кто будет онлайн сдавать.
+
[https://us06web.zoom.us/j/83617327188?pwd=uFWiZmkMbN37wUl27lQmLQuAkT4Bay.1 Ссылка] для тех, кто будет сдавать онлайн.
  
 
==== Правила контрольной работы  ====
 
==== Правила контрольной работы  ====
Строка 101: Строка 93:
 
3. Можно от руки написать на планшете и затем распечатать.
 
3. Можно от руки написать на планшете и затем распечатать.
  
−
<!--  
+
<!--
  
−
Аудитории R201 (240 чел.), R205 (122 чел.), R301 (240 чел.), R304 (192 чел.), R404 (192 чел.), R405 (122 чел.), R503 (112 чел.).
+
==== Распределение по аудиториям ====
  
 +
[https://drive.google.com/file/d/1T_llw5UMgtlIauw3uPtFONwwBpdPb8Yk/view?usp=sharing Модельный вариант]
  
 +
Аудитории R201 (240 чел.), R205 (122 чел.), R301 (240 чел.), R304 (192 чел.), R404 (192 чел.), R405 (122 чел.), R503 (112 чел.).
  
−
В контрольную 4 марта войдут 7 задач указанных типов.
 
  
 
  -->
 
  -->
  
 
== Коллоквиум ==
 
== Коллоквиум ==
−
 
−
[https://drive.google.com/file/d/1h2cnqCTsnd1UkQP6Wwsh0AMWRHMyzUjW/view?usp=sharing Программа коллоквиума]
 
−
 
−
[https://us06web.zoom.us/j/81977127622?pwd=3eMV9P5kxofTvHXWUsBQqzyzWVxADv.1 Cсылка] для тех, кто будет онлайн сдавать. Начало 14:00.
 
 
=== Расписание коллоквиума ===
 
=== Расписание коллоквиума ===
−
 
+
Коллоквиум состоится 21-го марта.
 
{| class="wikitable" style="text-align:center"
 
{| class="wikitable" style="text-align:center"
 
|-
 
|-
 
! Группа !! Время !! аудитория
 
! Группа !! Время !! аудитория
−
|-
+
|-
−
|| БПМИ231 || 10:00 || R405
+
||9:30 || БПМИ244 || R204
 +
|- 
 +
||11:30 || БПМИ243 || R204
 
|-  
 
|-  
−
|| БПМИ232 || 9:30 || R405
+
||9:30     || БПМИ245 || R205
−
|-
+
|-  
−
|| БПМИ233 || 13:00 || R407
+
||11:30 || БПМИ241 || R205
−
|-
+
|-  
−
|| БПМИ234 || 11:10 || R407
+
||13:30 || БПМИ242 || R205
 
|}
 
|}
 +
 +
 +
[https://drive.google.com/file/d/1o8El78SejNH3XXChgeBRUhR-2-5hAPFy/view?usp=sharing Программа коллоквиума]
  
 
=== Правила проведения коллоквиума===
 
=== Правила проведения коллоквиума===
Строка 152: Строка 146:
  
 
'''Замечание''': За списывание и использование любых носителей информации (электронных и бумажных), студент получает 0 за коллоквиум без возможности пересдачи.
 
'''Замечание''': За списывание и использование любых носителей информации (электронных и бумажных), студент получает 0 за коллоквиум без возможности пересдачи.
 +
 +
<!-- [https://drive.google.com/file/d/1h2cnqCTsnd1UkQP6Wwsh0AMWRHMyzUjW/view?usp=sharing Программа коллоквиума]
 +
 +
[https://us06web.zoom.us/j/81977127622?pwd=3eMV9P5kxofTvHXWUsBQqzyzWVxADv.1 Cсылка] для тех, кто будет онлайн сдавать. Начало 14:00.
 +
 +
=== Расписание коллоквиума ===
 +
 +
{| class="wikitable" style="text-align:center"
 +
|-
 +
! Группа !! Время !! аудитория
 +
|-
 +
|| БПМИ231 || 10:00 || R405
 +
|-
 +
|| БПМИ232 || 9:30 || R405
 +
|-
 +
|| БПМИ233 || 13:00 || R407
 +
|-
 +
|| БПМИ234 || 11:10 || R407
 +
|}
 +
 +
-->
  
 
== Экзамен ==
 
== Экзамен ==
 
   
 
   
−
Экзамен письменный, 29 марта 2024 г. Длительность 2.5 часа, начало в 11:00, аудитория R401.  
+
Экзамен письменный, 26 марта 2025 г. Длительность 2.5 часа, 14:40-17:10, аудитории R404 (группы 241+242+243), R405 (группы 244+245).  
−
[https://drive.google.com/file/d/1nXVSHd-NBFo0OoUbqI79wVThRt5I1FfI/view?usp=sharing Демо-версия]
+
 
 +
[https://drive.google.com/file/d/16sPt9nOa4Gy6-uCL3pD5ZmCPHlvwyDJy/view?usp=sharing Демо-версия]
 +
 
 +
1. С собой можно взять собственноручно написанную шпаргалку размера А4 (на одной его стороне). Можно от руки написать на планшете и затем распечатать.
 +
 
 +
2. Разрешается принести с собой калькулятор (непрограммируемый).
 +
 
 +
<!-- [https://us06web.zoom.us/j/87313108157?pwd=yJ0ojfmGF5jZXRepjStwGpdaOZHPJz.1 Cсылка] для тех, кто будет онлайн сдавать. R404 (190) R503 (110), R405 (108).-->
  
−
[https://us06web.zoom.us/j/87313108157?pwd=yJ0ojfmGF5jZXRepjStwGpdaOZHPJz.1 Cсылка] для тех, кто будет онлайн сдавать.
+
[https://us06web.zoom.us/j/81169938145?pwd=6nhsz2OpNbxHbACSplkYDRbblnLLBa.1 Cсылка] для тех, кто пишет онлайн.
  
 
== Оценка ==
 
== Оценка ==
Строка 180: Строка 202:
 
{| class="wikitable" style="text-align:center"
 
{| class="wikitable" style="text-align:center"
 
|-
 
|-
−
! [https://docs.google.com/spreadsheets/d/1rJl964CN7xT9efxP3IVwXYyn5IZQM0tNUHak3mbXEqw/edit#gid=519861771 БПМИ231] !! [https://docs.google.com/spreadsheets/d/1rJl964CN7xT9efxP3IVwXYyn5IZQM0tNUHak3mbXEqw/edit#gid=1558924741 БПМИ232] !! [https://docs.google.com/spreadsheets/d/1rJl964CN7xT9efxP3IVwXYyn5IZQM0tNUHak3mbXEqw/edit#gid=819769274 БПМИ233] !! [https://docs.google.com/spreadsheets/d/1rJl964CN7xT9efxP3IVwXYyn5IZQM0tNUHak3mbXEqw/edit#gid=1892256028 БПМИ234]  
+
! [https://docs.google.com/spreadsheets/d/10gk6R0WECuljkQ70abixkC1VGU_PcLgJrtq-KJ2pgn8/edit?gid=840627089#gid=840627089 БПМИ241] || [https://docs.google.com/spreadsheets/d/10gk6R0WECuljkQ70abixkC1VGU_PcLgJrtq-KJ2pgn8/edit?gid=1771040506#gid=1771040506 БПМИ242] || [https://docs.google.com/spreadsheets/d/10gk6R0WECuljkQ70abixkC1VGU_PcLgJrtq-KJ2pgn8/edit?gid=382422285#gid=382422285 БПМИ243]!![https://docs.google.com/spreadsheets/d/10gk6R0WECuljkQ70abixkC1VGU_PcLgJrtq-KJ2pgn8/edit?gid=538948281#gid=538948281 БПМИ244] !!  
 +
[https://docs.google.com/spreadsheets/d/10gk6R0WECuljkQ70abixkC1VGU_PcLgJrtq-KJ2pgn8/edit?gid=808431978#gid=808431978 БПМИ245]  
 
|}
 
|}
−
 
−
 
  
 
== Сводная таблица с оценками по ДЗ ==
 
== Сводная таблица с оценками по ДЗ ==
Строка 189: Строка 210:
 
{| class="wikitable" style="text-align:center"
 
{| class="wikitable" style="text-align:center"
 
|-
 
|-
−
! [https://docs.google.com/spreadsheets/d/11hPSBGwCcqxuyG3NVSKUeCQ8ZlPFLOlBSP6E6yR_RCs/edit#gid=519861771 БПМИ231] !! [https://docs.google.com/spreadsheets/d/11hPSBGwCcqxuyG3NVSKUeCQ8ZlPFLOlBSP6E6yR_RCs/edit#gid=922156151 БПМИ232] !! [https://docs.google.com/spreadsheets/d/11hPSBGwCcqxuyG3NVSKUeCQ8ZlPFLOlBSP6E6yR_RCs/edit#gid=1355444688 БПМИ233] !! [https://docs.google.com/spreadsheets/d/11hPSBGwCcqxuyG3NVSKUeCQ8ZlPFLOlBSP6E6yR_RCs/edit#gid=461313271 БПМИ234]  
+
! [https://docs.google.com/spreadsheets/d/15l4-II8SirJBuutZFoVbyF9QUDgsVzmzamF2mAvsVEE/edit?gid=0#gid=0 БПМИ241] || [https://docs.google.com/spreadsheets/d/15l4-II8SirJBuutZFoVbyF9QUDgsVzmzamF2mAvsVEE/edit?gid=61268542#gid=61268542 БПМИ242] || [https://docs.google.com/spreadsheets/d/15l4-II8SirJBuutZFoVbyF9QUDgsVzmzamF2mAvsVEE/edit?gid=710162730#gid=710162730 БПМИ243]!![https://docs.google.com/spreadsheets/d/15l4-II8SirJBuutZFoVbyF9QUDgsVzmzamF2mAvsVEE/edit?gid=764991279#gid=764991279 БПМИ244] !!  
 +
[https://docs.google.com/spreadsheets/d/15l4-II8SirJBuutZFoVbyF9QUDgsVzmzamF2mAvsVEE/edit?gid=766813518#gid=766813518 БПМИ245]  
 
|}
 
|}
 +
 +
== Полезные ссылки ==
 +
 +
[https://drive.google.com/file/d/1gSAJGCRom_DFr2rho0uzVLtPpVE8NTOi/view?usp=sharing Конспект лекций 2023 года.]
 +
 +
[[Теория чисел (пилотный поток) 2023/24]]
 +
 +
[[Криптография на решётках 24/25]] (факультатив, 4-й модуль 24/25 у.г.)
 +
 +
[[Дополнительные главы теории чисел]] (факультатив в 4-м модуле 22/23 у.г.)
  
 
==Книги==
 
==Книги==
Строка 209: Строка 241:
 
# [ВЭБ] [https://mathprofi.com/uploads/files/2581_f_41_e.b.vinberg-kurs-algebry-2-e-izd.pdf Винберг Э. Б. Курс алгебры]
 
# [ВЭБ] [https://mathprofi.com/uploads/files/2581_f_41_e.b.vinberg-kurs-algebry-2-e-izd.pdf Винберг Э. Б. Курс алгебры]
 
# Герман, О. Н., Нестеренко, Ю. Теоретико-числовые методы в криптографии 2012
 
# Герман, О. Н., Нестеренко, Ю. Теоретико-числовые методы в криптографии 2012
 +
# Гашков С. Б., Применко Э. А., Черепнев М. А. Криптографические методы защиты информации, Академия, 2010
 
# Глухов М. М., Круглов И.А., Пичкур А.Б., Черёмушкин А.В. Введение в теоретико-числовые методы криптографии Лань, 2011
 
# Глухов М. М., Круглов И.А., Пичкур А.Б., Черёмушкин А.В. Введение в теоретико-числовые методы криптографии Лань, 2011
 
# Кнут, Д. Е. Искусство программирования для ЭВМ. Том 2: Получисленные алгоритмы "Вильямс" , М., Санкт-Петербург, Киев, 2000
 
# Кнут, Д. Е. Искусство программирования для ЭВМ. Том 2: Получисленные алгоритмы "Вильямс" , М., Санкт-Петербург, Киев, 2000

Текущая версия на 21:23, 30 марта 2025

О курсе

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

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

Группа БПМИ241 БПМИ242 БПМИ243 БПМИ244 БПМИ245
Лектор А.В. Устинов
Семинарист Ожегов Фёдор Юрьевич А.В. Устинов А. Калмынин Бельдиев Иван Сергеевич
Ассистент Заварин Александр Сергеевич Лейла Мурсманидзе Горбач Елизавета Леонидовн Заварин Александр Сергеевич Грецкая Вера Ильинична
Ассистент лектора Агаев Мурад

Лекции

Конспект лекций.

Лекция 1 (10.01.2025) Основная теорема арифметики. Сравнения и их свойства. Полная и приведённая системы вычетов. Определение группы. Примеры групп. Определение кольца. Примеры колец. Кольцо вычетов. Группа обратимых элементов кольца вычетов. Малая теорема Ферма и теорема Эйлера. Теорема Вильсона.

Лекция 2 (17.01.2025) Мультипликативные функции. Мультипликативность функции Эйлера. Тест "Ферма". Псевдопростые числа Ферма. Числа Кармайкла. Тест сильной псевдопростоты. Теорема Рабина (без доказательства). Криптосистема RSA. Электронная подпись RSA.

Лекция 3 (24.01.2025) Асимметричная криптография. Гомоморфное шифрование. Слепая подпись RSA. Забывчивая передача RSA. Китайская теорема об остатках (КТО), три доказательства. Изоморфизмы групп и колец. Прямое произведение групп и колец. КТО как изоморфизм колец вычетов.

Лекция 4 (31.01.2025) Делители нуля. Деление многочленов с остатком. Теорема Безу. Теорема о числе корней многочлена над полем. Расширенный алгоритм Евклида для многочленов. НОД многочленов. Однозначность разложения многочлена в произведение неприводимых. КТО для многочленов. Связь с интерполяционным многочленом Лагранжа. Циклические группы.

Лекция 5 (07.02.2025) Первообразные корни (ПК). Критерий ПК. Существование ПК по простому модулю. Существование ПК по модулю p^2. Существование ПК по модулю p^a. Существование ПК по модулю 2p^a.

Лекция 6 (13.02.2025, вместо 14.02.2025) Индексы. Задача дискретного логарифмирования. Протокол Диффи -- Хеллмана. Вычислительная задача Диффи -- Хеллмана. Протокол Эль-Гамаля. Полиномиально сводимые и вычислительно эквивалентные функции. Вычислительная эквивалентность задач DH и EG. Трёхэтапный протокол Шамира. Квадратичные вычеты. Критерий Эйлера. Символ Лежандра. Простейшие свойства символа Лежандра. Критерий Гаусса.

Лекция 7 (21.02.2025) Квадратичный закон взаимности. Символ Якоби и его свойства. Теорема Лагранжа о порядке подгруппы (без доказательства). Тест Соловея -- Штрассена. Оценка числа оснований, для которых тест Соловея -- Штрассена не срабатывает. Псевдопростые числа Эйлера.

Лекция 8 (28.02.2025) Извлечение квадратного корня по модулю простого числа p=4k+3. Числа Блюма. Криптосистема Рабина, шифрование и электронная подпись. Эквивалентность задач факторизации числа Блюма n и извлечения квадратного корня по модулю n. Забывчивая передача Рабина. Протоколы привязки к биту и подбрасывания монеты по телефону. Подбрасывания монеты по телефону с помощью чисел Блюма. Криптосистема Гольдвассер -- Микали: протоколы привязки к биту и шифрования. Гомоморфность криптосистем RSA, Рабина, Эль-Гамаля и Гольдвассер -- Микали.

Лекция 9 (07.03.2025) Генератор Блюм -- Блюма -- Шуба. Вероятностное шифрование Блюма -- Гольдвассер. Лемма Гензеля. Подъём решений полиномиальных сравнений.

Лекция 10 (14.03.2025) Вероятностное шифрование. Криптосистема Пэйе.

Семинары и домашние задания

Семинар + ДЗ 1, Семинар + ДЗ 2, Семинар + ДЗ 3, Семинар + ДЗ 4, Семинар + ДЗ 5, Семинар + ДЗ 6, Семинар + ДЗ 7, Семинар + ДЗ 8, Семинар + ДЗ 9, Семинар 10

ДЗ 10 (на каникулы)


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

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

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

Всё должно быть написано аккуратно и понятно. Ассистент имеет право вызвать студента на защиту задания, если решение неясное или есть подозрение на списывание или использование ИИ. В случае неявки или невозможности объяснить решение студент получает 0 баллов.

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

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

21 февраля 18:10-19:30.

Распределение по аудиториям R201 (241, 242, 243) и R204 (244, 245).

Темы: теоремы Ферма, Эйлера, Вильсона; псевдопростые числа; числа Кармайкла; китайская теорема об остатках для чисел и многочленов; первобразные корни и индексы.

Демо-вариант

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

Ссылка для тех, кто будет сдавать онлайн.

Правила контрольной работы

1. Допускается использование листа формата А4 для записей, однако писать разрешается только на одной его стороне.

2. Разрешается принести с собой калькулятор.

3. Можно от руки написать на планшете и затем распечатать.


Коллоквиум

Расписание коллоквиума

Коллоквиум состоится 21-го марта.

Группа Время аудитория
9:30 БПМИ244 R204
11:30 БПМИ243 R204
9:30 БПМИ245 R205
11:30 БПМИ241 R205
13:30 БПМИ242 R205


Программа коллоквиума

Правила проведения коллоквиума

Коллоквиум проходит в виде беседы со студентом, в которой студент рассказывает ответы на вопросы билета, а принимающий имеет возможность задавать любые уточняющие вопросы в рамках билета.

Билет будет состоять из следующих частей (максимально 9 баллов):

  1. два определения (по 1 баллу каждое);
  2. формулировки двух теорем без доказательства (по 1 баллу каждая);
  3. две теоремы с доказательствами (по 2.5 баллу каждое).

Если за ответ по билету было набрано 7,5-9 баллов, то студент имеет возможность запросить у проверяющего дополнительную сложную задачу (на 2 балла), которую проверяющий выбирает из списка дополнительных задач сам. Дополнительные задачи заранее не известны.
Замечание: Эта задача дается только в том случае, если студент набрал 7,5-9 баллов за все остальные части билета. Задача не прописана в билете, она выдается проверяющим.

Время подготовки билета На подготовку вопрос из билета (пунктов 1-3) 40 минут. Беседа с преподавателем идет не больше 40 минут. После беседы с преподавателем, если студент набирает 7,5-9 баллов, дается ещё до 20 минут на решение сложной задачи. Студент максимально может потратить 1 час и 45 минут на сдачу коллоквиума.

Оценка за коллоквиум равна минимуму из 10 и набранного числа баллов.

Замечание: За списывание и использование любых носителей информации (электронных и бумажных), студент получает 0 за коллоквиум без возможности пересдачи.


Экзамен

Экзамен письменный, 26 марта 2025 г. Длительность 2.5 часа, 14:40-17:10, аудитории R404 (группы 241+242+243), R405 (группы 244+245).

Демо-версия

1. С собой можно взять собственноручно написанную шпаргалку размера А4 (на одной его стороне). Можно от руки написать на планшете и затем распечатать.

2. Разрешается принести с собой калькулятор (непрограммируемый).


Cсылка для тех, кто пишет онлайн.

Оценка

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

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

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

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

Ведомость

БПМИ241 БПМИ242 БПМИ243 БПМИ244

БПМИ245

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

БПМИ241 БПМИ242 БПМИ243 БПМИ244

БПМИ245

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

Конспект лекций 2023 года.

Теория чисел (пилотный поток) 2023/24

Криптография на решётках 24/25 (факультатив, 4-й модуль 24/25 у.г.)

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

Книги

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

  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. Гашков С. Б., Применко Э. А., Черепнев М. А. Криптографические методы защиты информации, Академия, 2010
  5. Глухов М. М., Круглов И.А., Пичкур А.Б., Черёмушкин А.В. Введение в теоретико-числовые методы криптографии Лань, 2011
  6. Кнут, Д. Е. Искусство программирования для ЭВМ. Том 2: Получисленные алгоритмы "Вильямс" , М., Санкт-Петербург, Киев, 2000
  7. Коблиц Н. Курс теории чисел и криптографии. М.: ТВП, 2001.
  8. Нестеренко Ю. В., Теория чисел
  9. Ященко, В. В. (ред.) Введение в криптографию, МЦНМО, Москва, 1999
  10. Hoffstein, J.; Pipher, J., Silverman, J. H. An introduction to mathematical cryptography Springer, 2008,
Источник — «http://wiki.cs.hse.ru/index.php?title=Теория_чисел_(пилотный_поток)_2024/25&oldid=90335»