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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показано 75 промежуточных версии 2 участников)
Строка 2: Строка 2:
  
 
Это курс основ теории чисел, который содержит такие базовые разделы как алгоритм Евклида, цепные дроби, арифметические функции, теория сравнений, квадратичные вычеты, первообразные корни. Параллельно будет происходить знакомство с задачами математической криптографии и простейшими криптографическими протоколами.
 
Это курс основ теории чисел, который содержит такие базовые разделы как алгоритм Евклида, цепные дроби, арифметические функции, теория сравнений, квадратичные вычеты, первообразные корни. Параллельно будет происходить знакомство с задачами математической криптографии и простейшими криптографическими протоколами.
−
 
−
=== Предварительная программа ===
 
−
 
−
# Алгоритмы и их сложность. Классические алгоритмы целочисленной арифметики. Быстрый алгоритм возведения в степень.
 
−
# Алгоритм Евклида и его варианты. Теорема Ламе. Расширенный алгоритм Евклида.
 
−
# Конечные цепные дроби. Свойства подходящих дробей.
 
−
# Бесконечные цепные дроби. Однозначность представления действительных чисел цепными дробями. Теорема Лагранжа.
 
−
# Теория сравнений. Кольцо вычетов. Группа обратимых кольца вычетов. Теорема Вильсона. Функция Эйлера. Теоремы Ферма и Эйлера. [Простейшие детерминированные и вероятностные тесты на простоту. Псевдопростые, абсолютно псевдопростые и сильно псевдопростые числа. Понятие о криптографии с открытым ключом. Система шифрования RSA. Криптосистема Эль-Гамаля.]
 
−
# Китайская теорема об остатках. Решение систем линейных сравнений. Решение полиномиальных сравнений. [Криптосистема Рабина и её модификации. ]
 
−
# Квадратичные вычеты. Свойства символов Лежандра и Якоби. Квадратичный закон взаимности. [Тест Соловея--Штрассена. Псевдопростые числа Эйлера. Протоколы, использующие свойства символа Якоби. Генератор Блюм -- Блюма -- Шуба. Криптосистема Блюма -- Гольдвассер. Криптосистема Гольдвассер -- Микали.]
 
−
# Первообразные корни и индексы. Структура группы $\mathbb{Z}^*_m$ для произвольного $m$ [Метод Диффи-Хеллмана. Дискретное логарифмирование. Протоколы аутентификации и "подбрасывание монеты по телефону". Хеш-функция Шаума -- Хайста -- Пфитсман.]
 
−
# Интерполяционный многочлен Лагранжа и его связь с китайской теоремой об остатках. Умножение Карацубы. [Разделение секрета Шамира.]
 
−
# Дискретное преобразование Фурье. Быстрое преобразование Фурье.
 
  
 
=== Полезные ссылки ===
 
=== Полезные ссылки ===
Строка 20: Строка 7:
 
[[Дополнительные главы теории чисел]] (курс в 4-м модуле 2022-2023 у.г.)
 
[[Дополнительные главы теории чисел]] (курс в 4-м модуле 2022-2023 у.г.)
  
−
=== Семинары ===
+
=== Преподаватели и учебные ассистенты ===
−
 
+
{| 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]
−
=== Ассистенты ===
+
|-
−
 
+
|| Лектор ||colspan="4"| [https://t.me/AlexeyVUstinov А.В. Устинов]
−
 
+
|-
 +
|| Семинарист || [https://t.me/AlexeyVUstinov А.В. Устинов] ||colspan="2" | А. Калмынин || Ф. Ожегов
 +
|-
 +
|| Ассистент || [https://t.me/TigodanAC Окунев Данила] || [https://t.me/oleja_shpep Рябов Олег] || [https://t.me/andreyvoyko04 Войко Андрей] || [https://t.me/raspberru Грецкая Вера]
 +
|-
 +
|| Ассистент лектора || colspan="4" | [https://t.me/citizen_murad Агаев Мурад]
 +
|-
 +
|}
  
 
=== Правила выставления оценок ===
 
=== Правила выставления оценок ===
Строка 36: Строка 30:
  
 
Всё должно быть написано аккуратно и понятно.
 
Всё должно быть написано аккуратно и понятно.
 +
 +
ПРОСРОЧКА: У Вас есть возможность дважды отправить домашнее задание после истечения срока сдачи в течение 24 часов. Однако этот шанс не может быть использован для сдачи последнего домашнего задания.
  
 
== Лекции ==
 
== Лекции ==
  
−
Лекция 1 (12.01.2023) Сложность алгоритмов. Алгоритм Евклида. Теорема Ламе. Расширенный алгоритм Евклида. [A]
+
[https://drive.google.com/file/d/1gSAJGCRom_DFr2rho0uzVLtPpVE8NTOi/view?usp=sharing Конспект лекций прошлого года.]
  
−
Лекция 2 (19.01.2023) Основная теорема арифметики. Уравнение ax+by=c. Цепные дроби. Представление рациональных чисел конечными цепными дробями. Рекуррентные соотношения на числители и знаменатели подходящих дробей. [Б, ВИМ,Х]
+
Лекция 1 (12.01.2024) Основная теорема арифметики. Определение кольца. Сложность алгоритмов. Алгоритм Евклида. Расширенный алгоритм Евклида. Решение уравнения Уравнение ax+by=1 с помощью цепных дробей. [A]
  
−
Лекция 3 (26.01.2023) Свойства подходящих дробей. Бесконечные цепные дроби. Приближение чисел подходящими дробями. Теорема Лежандра (критерий подходящей дроби).[Б, ВИМ, Х]
+
Лекция 2 (19.01.2024) Оценка числа шагов в алгоритме Евклида. Оценка сложности алгоритма Евклида. Общий вид решения уравнения ax+by=c. Мультипликативные функции. Свёртка Дирихле. Формула обращения Мёбиуса. Функция Эйлера. Тождество Гаусса. Формула для функции Эйлера. [AР,Б,ВИМ]
  
−
Лекция 4 (02.02.2023) Теорема Лежандра (критерий подходящей дроби). Сравнения и их свойства. Полная и приведённая системы вычетов. Функция Эйлера. Теорема Эйлера. Малая теорема Ферма. Псевдопростые числа Ферма.  
+
Лекция 3 (25.01.2024, вместо 02.02.2024) Ряды Дирихле. Дзета-функция Римана. Ряды Дирихле для простейших мультипликативных функций. Сравнения и их свойства. Полная и приведённая системы вычетов. Кольцо вычетов. Определение группы. Примеры групп. Группа обратимых элементов кольца вычетов. [Б,ВИМ]
  
−
Лекция 5 (03.02.2023) Тест "Ферма". Числа Кармайкла. Китайская теорема об остатках (два доказательства). Группы, кольца, поля. Кольцо вычетов. Группа обратимых элементов кольца вычетов. [ВЭБ]
+
Лекция 4 (26.01.2024) Группа обратимых элементов кольца с единицей. Поле вычетов по простому модулю. Малая теорема Ферма и теорема Эйлера. Псевдопростые числа. Числа Кармайкла. Деление многочленов с остатком. Теорема о числе корней многочлена. Теорема Вильсона.
  
−
Лекция 6 (16.02.2023) Теорема о числе корней многочлена над полем. Теорема Вильсона. Тест сильной псевдопростоты. Изоморфизм групп. Изоморфизм колец. Прямое произведение групп. Прямое произведение колец. Китайская теорема об остатках как изоморфизм колец. Мультипликативность функции Эйлера. Формула для вычисления функции Эйлера. [НК]
+
Лекция 5 (09.02.2024) Тест сильной псевдопростоты. Сильно псевдопростые числа. Китайская теорема об остатках (три доказательства). Изоморфизм групп. Изоморфизм колец. Криптосистема RSA. Электронная подпись RSA.
  
−
(23.02.2023) Лекция пропала из-за праздника.
+
Лекция 6 (16.02.2024) Подгруппы. Циклические группы. Порядок группы и порядок элемента. Теорема Лагранжа (без доказательства). Первообразные корни (ПК). Критерий ПК. Усиленная теорема Эйлера и её следствие. Теорема о существовании ПК по модулю простого числа.
  
−
Лекция 7 (02.03.2023) RSA, шифрование + ЭЦП. Понятие о криптографии с открытым ключом. [MOV] Подгруппы. Теорема Лагранжа о порядке подгруппы. Циклические группы. [ВЭБ]
+
Лекция 7 (22.02.2024, вместо 23.02.2024) ПК по модулям p^2, p^a, 2p^a. Индексы и их свойства. Задача дискретного логарифмирования. Односторонние функции. Протокол Диффи -- Хеллмана. Вычислительная задача Диффи -- Хеллмана DH. Схема шифрования Эль Гамаля. Задача вскрытия схемы шифрования Эль Гамаля EG. Протокол Мэсси -- Омуры. Полиномиально сводимые и полиномиально эквивалентные функции. Полиномиальная эквивалентность функций DH и EG.  
  
−
Лекция 8 (09.03.2023) Следствия теоремы Лагранжа. Первообразные корни (ПК). Критерий ПК. Индексы и их свойства. Криптосистемы Диффи -- Хеллмана и Эль Гамаля. Квадратичные вычеты. Критерий Эйлера.
+
Лекция 8 (29.02.2024) Квадратичные вычеты. Символ Лежандра и его свойства. Квадратичный закон взаимности. Символ Якоби и его свойства.
  
−
Лекция 9 (16.03.2023) Символ Лежандра. Простейшие свойства символа Лежандра. Квадратичный закон взаимности. Символ Якоби.  
+
Лекция 9 (07.03.2024, вместо 08.03.2024) Тест Соловея -- Штрассена. Псевдопростые числа Эйлера. Оценка числа псевдопростых чисел Эйлера. Тест Миллера -- Рабина (тест сильной псевдопростоты). Теорема Рабина (без доказательства). Связь между разными типами псевдопростых чисел (без доказательства). Протоколы привязки к биту. Привязка к биту Гольдвассер -- Микали.  
  
−
Лекция 10 (17.03.2023) Свойства символа Якоби. Псевдопростые числа Эйлера. Тест Соловея -- Штрассена. Протоколы привязки к биту. Привязка к биту Гольдвассер -- Микали. Шифрование Гольдвассер -- Микали. Криптосистема Гольдвассер -- Микали как криптосистема гомоморфного шифрования.
+
Лекция 10 (15.03.2024) Шифрование Гольдвассер -- Микали. Псевдослучайный генератор Блюм -- Блюма -- Шуба. Вероятностное шифрование Блюма -- Гольдвассер. Криптосистема Рабина, шифрование и электронная подпись. Подбрасывание монетки с помощью криптосистемы Рабина. Забывчивая передача Рабина. Гомоморфное шифрование, примеры (RSA, EG, Рабин, Гольдвассер -- Микали).
−
 
+
−
[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/1W3rmNbAIA9keq-CpPCbfzprtx20ucwod/view?usp=sharing Семинар 1]
−
[https://drive.google.com/file/d/1xcAMuIxRweXe2OwquLAFet1i_FlGYsoO/view?usp=share_link Семинар 1],
+
[https://drive.google.com/file/d/1mCwUMderXKTTRjNvYaGTxka0q_N7OF-d/view?usp=sharing Семинар 2]
−
[https://drive.google.com/file/d/1JeP_i33HVjYh4xa5f4OTh6k8pmEwbMSW/view?usp=sharing Семинар 2],
+
[https://drive.google.com/file/d/11Zf1FgdW5ShCbiecZjXbLJfNvAg0bXJc/view?usp=sharing Семинар 3]
−
[https://drive.google.com/file/d/1si29qrjb8-IwjinOQ9RGZrsah_kuGb1m/view?usp=sharing Семинар 3],
+
[https://drive.google.com/file/d/1SKltrMSKEOIPku-3kFnZXIrsIuP6osv4/view?usp=sharing Семинар 4]
−
[https://drive.google.com/file/d/1icEzaxof7azcl9TYl2zKLXBzIEVJkLN3/view?usp=sharing Семинар 4],
+
[https://drive.google.com/file/d/1m8pVTW21YU8yTf2iBfhc7NFlB3vDfUeZ/view?usp=sharing Семинар 5]
−
[https://drive.google.com/file/d/1qACnKnAN_5q8YoTZUALBuzCiguuFM61h/view?usp=sharing Семинар 5],
+
[https://drive.google.com/file/d/1C4O6EC1XeL94J5TcFYjaqgXJNWJXXtlv/view?usp=sharing Семинар 6]
−
[https://drive.google.com/file/d/15ixVi9n-0LoJXE-Po17-4A8g0FpFhlrx/view?usp=sharing Семинар 6],
+
[https://drive.google.com/file/d/1m17206JOrKK8Zs7TAGYyZHAPfL44oQ4X/view?usp=sharing Семинар 7]
−
[https://drive.google.com/file/d/1MkS5kSDqtb7kZg1ji5tuvFjz-AFdW8_k/view?usp=sharing Семинар 7],
+
[https://drive.google.com/file/d/1TQBX-p0BwKpz21GT_rJULfo6bUCGZpV3/view?usp=sharing Семинар 8]
−
[https://drive.google.com/file/d/11e7Wsz2EurOXg1tYHDxUQCmnlLp--XBt/view?usp=sharing Семинар 8],
+
[https://drive.google.com/file/d/1woRlFLeqKkdwj00pNYPdNeFvndaE3uY5/view?usp=sharing Семинар 9]
−
[https://drive.google.com/file/d/11U6uqMNbu6FHG4gGFu-AFM3SsK-Gc7-6/view?usp=sharing Семинар 9],
+
[https://drive.google.com/file/d/1ozA8yd5xNb7Tb45tfCOPfdkIo2JgHj0J/view?usp=sharing Семинар 10] <!--  -->
−
[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/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]
−
[https://drive.google.com/file/d/13hXP1H-wbsXtsnu-ClMKzTTeH57iUgRe/view?usp=sharing ДЗ-3]
+
[https://drive.google.com/file/d/1hxfHOpiQoMwvFwyEhC37s5z2w3tpXix8/view?usp=sharing ДЗ-6]
−
[https://drive.google.com/file/d/1B6grzE-KcVaTZSAt1LaCmdCWswqDk4f2/view?usp=sharing ДЗ-4]
+
[https://drive.google.com/file/d/1vuVDI5yz7aD-s1v_98QpQAm-blcC8GeG/view?usp=sharing ДЗ-7]
−
[https://drive.google.com/file/d/1qlLxOB7-6wnU_oarM8DTp3lgFocX7pea/view?usp=sharing ДЗ-5]
+
[https://drive.google.com/file/d/1L0lWnVI5zbBjVZdWDMFsc3g1vvkWO0IB/view?usp=sharing ДЗ-8]
−
[https://drive.google.com/file/d/1vt4JST4uWx47G-WNFrtU7G1FKRJmqMvp/view?usp=sharing ДЗ-6]
+
[https://drive.google.com/file/d/1XZ21Ony4UqtWdJS_HYxTRc7sRLl5Wfaf/view?usp=sharing ДЗ-9] <!-- -->
−
[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.  
+
Контрольная работа 2 марта (суббота) в 11:10, длительность - 1:30.  
  
−
Аудитории R201 (240 чел.), R205 (122 чел.), R301 (240 чел.), R304 (192 чел.), R404 (192 чел.), R405 (122 чел.), R503 (112 чел.).
+
==== Распределение по аудиториям ====
 +
R401 - БПМИ231, БПМИ234
  
−
[https://disk.yandex.ru/i/u9zxkP-37spzcg Контрольная - обобщённый модельный вариант]
+
R404 - БПМИ232, БПМИ233
  
−
В контрольную 4 марта войдут 7 задач указанных типов.
+
[https://drive.google.com/file/d/1T_llw5UMgtlIauw3uPtFONwwBpdPb8Yk/view?usp=sharing Модельный вариант]
  
 
Дистанционное участие возможно для тех, у кого есть уважительная причина, подтверждённая учебным офисом (болезнь, дистанционное обучение, участие в важной олимпиаде).  
 
Дистанционное участие возможно для тех, у кого есть уважительная причина, подтверждённая учебным офисом (болезнь, дистанционное обучение, участие в важной олимпиаде).  
 
Перед экзаменом преподаватели должны иметь подтверждение из учебного офиса, что у студента есть уважительная причина.
 
Перед экзаменом преподаватели должны иметь подтверждение из учебного офиса, что у студента есть уважительная причина.
 +
 +
[https://us06web.zoom.us/j/81522212645?pwd=mlNMksCHuzArr8v062S5BJluRGRolJ.1 Ссылка] для тех, кто будет онлайн сдавать.
 +
 +
==== Правила контрольной работы  ====
 +
 +
1. Допускается использование листа формата А4 для записей, однако писать разрешается только на одной его стороне.
 +
 +
2. Разрешается принести с собой калькулятор.
 +
 +
3. Можно от руки написать на планшете и затем распечатать.
 +
 +
<!--
 +
 +
Аудитории 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.
 +
=== Расписание коллоквиума ===
 +
 +
{| class="wikitable" style="text-align:center"
 +
|-
 +
! Группа !! Время !! аудитория
 +
|-
 +
|| БПМИ231 || 10:00 || R405
 +
|-
 +
|| БПМИ232 || 9:30 || R405
 +
|-
 +
|| БПМИ233 || 13:00 || R407
 +
|-
 +
|| БПМИ234 || 11:10 || R407
 +
|}
 +
 +
=== Правила проведения коллоквиума===
 +
 +
Коллоквиум проходит в виде беседы со студентом, в которой студент рассказывает ответы на вопросы билета, а принимающий имеет возможность задавать любые уточняющие вопросы в рамках билета.
 +
 +
'''Билет''' будет состоять из следующих частей (максимально 9 баллов):
 +
#два определения (по 1 баллу каждое);
 +
#формулировки двух теорем без доказательства (по 1 баллу каждая);
 +
#две теоремы с доказательствами (по 2.5 баллу каждое).
 +
 +
Если за ответ по билету было набрано '''7,5-9 баллов''', то студент имеет возможность запросить у проверяющего '''дополнительную сложную задачу (на 2 балла)''', которую проверяющий выбирает из списка дополнительных задач сам. Дополнительные задачи заранее не известны.<br/>
 +
'''Замечание''': Эта задача дается только в том случае, если студент набрал 7,5-9 баллов за все остальные части билета. Задача не прописана в билете, она выдается проверяющим.
 +
 +
'''Время подготовки билета'''
 +
На подготовку вопрос из билета (пунктов 1-3) '''40 минут'''.
 +
Беседа с преподавателем идет не больше '''40 минут'''.
 +
После беседы с преподавателем, если студент набирает 7,5-9 баллов, дается ещё '''до 20 минут''' на решение сложной задачи.
 +
Студент максимально может потратить '''1 час и 45 минут''' на сдачу коллоквиума.
 +
 +
'''Оценка за коллоквиум''' равна минимуму из 10 и набранного числа баллов.
 +
 +
'''Замечание''': За списывание и использование любых носителей информации (электронных и бумажных), студент получает 0 за коллоквиум без возможности пересдачи.
  
 
== Экзамен ==
 
== Экзамен ==
−
Экзамен письменный, 2.5 часа.  
+
−
[https://drive.google.com/file/d/1fC2aFymBJCi9Di9xlNjkdxtxjiGxDgNp/view?usp=sharing Билеты к экзамену (с баллами).]
+
Экзамен письменный, 29 марта 2024 г. Длительность 2.5 часа, начало в 11:00, аудитория R401.  
−
Модельные задачи в последнем билете.
+
[https://drive.google.com/file/d/1nXVSHd-NBFo0OoUbqI79wVThRt5I1FfI/view?usp=sharing Демо-версия]
 +
 
 +
[https://us06web.zoom.us/j/87313108157?pwd=yJ0ojfmGF5jZXRepjStwGpdaOZHPJz.1 Cсылка] для тех, кто будет онлайн сдавать.
  
 
== Оценка ==
 
== Оценка ==
  
−
Итог = min(10, Округление(0.25 * ДЗ + 0.25 * КР + 0.5 * Э)),
+
В течение года установлены следующие формы контроля:
−
где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, Э — оценка за экзамен.
+
* один письменный экзамен (ЭК), в сессию после модуля;
 +
* одна письменная контрольная работа (KР), которую планируется провести в середине 3-го модуля;
 +
* один коллоквиум (KЛ), который планируется провести в конце 3-го модуля;
 +
* около 10 домашних заданий (ДЗ, где ДЗ --- есть среднее арифметическое оценок всех домашних работ); обычно домашнее задание выдается к каждому семинару.
 +
 
 +
Накопленная Оценка, НО, вычисляется без округления по следующей формуле:
 +
НО = 0.4 * ДЗ + 0.2 * Кр + 0.4 * КЛ.
 +
Итоговая Оценка за Курс, ИО, вычисляется по следующей формуле:
 +
ИО = Округление(7/10*НО + 3/10*ЭК),
 +
 
 +
где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, ЭК — оценка за экзамен, КЛ —  оценка за коллоквиум.
 +
Если НО не меньше 8 (без округления), то студент может не сдавать экзамен. В этом случае ИО = Округление(НО).
 
Округление арифметическое.
 
Округление арифметическое.
  
 +
== Ведомость ==
 +
{| 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]
 +
|}
 +
 +
 +
 +
== Сводная таблица с оценками по ДЗ ==
 +
 +
{| 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]
 +
|}
  
 
==Книги==
 
==Книги==
 
===Основная литература===
 
===Основная литература===
 +
# [АР] [http://ega-math.narod.ru/Books/Ireland.htm Айерленд К. Роузен, М. Классическое введение в современную теорию чисел. - М.: Мир, 1998.]
 
# [A] [https://www.studmed.ru/akritas-ag-osnovy-kompyuternoy-algebry-s-prilozheniyami_4cf6c2ced74.html Акритас А.Г. Основы компьютерной алгебры с приложениями. 1994]
 
# [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://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://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://math.ru/lib/book/djvu/vinogradov.djvu Виноградов И. М., Основы теории чисел.]
 
# [НК] [https://www.studmed.ru/noden-p-kitte-k-algebraicheskaya-algoritmika-s-uprazhneniyami-i-resheniyami-_dc06f6ef316.html Ноден П., Китте К. Алгебраическая алгоритмика]
 
# [НК] [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]
 
# [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]
  
Строка 130: Строка 207:
  
 
# [https://techlibrary.ru/b/2j1a1s1j1m1f1o1l1p_2w.2v._3a1f1p1r1f1t1j1l1p-1y1j1s1m1p1c2c1f_1a1m1d1p1r1j1t1n2c_1c_1l1r1j1q1t1p1d1r1a1v1j1j._2003.pdf Василенко, О. Н. Теоретико-числовые методы в криптографии МЦНМО, 2003]
 
# [https://techlibrary.ru/b/2j1a1s1j1m1f1o1l1p_2w.2v._3a1f1p1r1f1t1j1l1p-1y1j1s1m1p1c2c1f_1a1m1d1p1r1j1t1n2c_1c_1l1r1j1q1t1p1d1r1a1v1j1j._2003.pdf Василенко, О. Н. Теоретико-числовые методы в криптографии МЦНМО, 2003]
 +
# [ВЭБ] [https://mathprofi.com/uploads/files/2581_f_41_e.b.vinberg-kurs-algebry-2-e-izd.pdf Винберг Э. Б. Курс алгебры]
 
# Герман, О. Н., Нестеренко, Ю. Теоретико-числовые методы в криптографии 2012
 
# Герман, О. Н., Нестеренко, Ю. Теоретико-числовые методы в криптографии 2012
 
# Глухов М. М., Круглов И.А., Пичкур А.Б., Черёмушкин А.В. Введение в теоретико-числовые методы криптографии Лань, 2011
 
# Глухов М. М., Круглов И.А., Пичкур А.Б., Черёмушкин А.В. Введение в теоретико-числовые методы криптографии Лань, 2011

Текущая версия на 00:05, 29 марта 2024

О курсе

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

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

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

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

Группа БПМИ231 БПМИ232 БПМИ233 БПМИ234
Лектор А.В. Устинов
Семинарист А.В. Устинов А. Калмынин Ф. Ожегов
Ассистент Окунев Данила Рябов Олег Войко Андрей Грецкая Вера
Ассистент лектора Агаев Мурад

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

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

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

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

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

Лекции

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

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

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

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

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

Лекция 5 (09.02.2024) Тест сильной псевдопростоты. Сильно псевдопростые числа. Китайская теорема об остатках (три доказательства). Изоморфизм групп. Изоморфизм колец. Криптосистема RSA. Электронная подпись RSA.

Лекция 6 (16.02.2024) Подгруппы. Циклические группы. Порядок группы и порядок элемента. Теорема Лагранжа (без доказательства). Первообразные корни (ПК). Критерий ПК. Усиленная теорема Эйлера и её следствие. Теорема о существовании ПК по модулю простого числа.

Лекция 7 (22.02.2024, вместо 23.02.2024) ПК по модулям p^2, p^a, 2p^a. Индексы и их свойства. Задача дискретного логарифмирования. Односторонние функции. Протокол Диффи -- Хеллмана. Вычислительная задача Диффи -- Хеллмана DH. Схема шифрования Эль Гамаля. Задача вскрытия схемы шифрования Эль Гамаля EG. Протокол Мэсси -- Омуры. Полиномиально сводимые и полиномиально эквивалентные функции. Полиномиальная эквивалентность функций DH и EG.

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

Лекция 9 (07.03.2024, вместо 08.03.2024) Тест Соловея -- Штрассена. Псевдопростые числа Эйлера. Оценка числа псевдопростых чисел Эйлера. Тест Миллера -- Рабина (тест сильной псевдопростоты). Теорема Рабина (без доказательства). Связь между разными типами псевдопростых чисел (без доказательства). Протоколы привязки к биту. Привязка к биту Гольдвассер -- Микали.

Лекция 10 (15.03.2024) Шифрование Гольдвассер -- Микали. Псевдослучайный генератор Блюм -- Блюма -- Шуба. Вероятностное шифрование Блюма -- Гольдвассер. Криптосистема Рабина, шифрование и электронная подпись. Подбрасывание монетки с помощью криптосистемы Рабина. Забывчивая передача Рабина. Гомоморфное шифрование, примеры (RSA, EG, Рабин, Гольдвассер -- Микали).

Семинары

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

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

ДЗ-1 ДЗ-2 ДЗ-3 ДЗ-4 ДЗ-5 ДЗ-6 ДЗ-7 ДЗ-8 ДЗ-9

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

Контрольная работа 2 марта (суббота) в 11:10, длительность - 1:30.

Распределение по аудиториям

R401 - БПМИ231, БПМИ234

R404 - БПМИ232, БПМИ233

Модельный вариант

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

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

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

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

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

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


Коллоквиум

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

Cсылка для тех, кто будет онлайн сдавать. Начало 14:00.

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

Группа Время аудитория
БПМИ231 10:00 R405
БПМИ232 9:30 R405
БПМИ233 13:00 R407
БПМИ234 11:10 R407

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

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

Билет будет состоять из следующих частей (максимально 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 за коллоквиум без возможности пересдачи.

Экзамен

Экзамен письменный, 29 марта 2024 г. Длительность 2.5 часа, начало в 11:00, аудитория R401. Демо-версия

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

Оценка

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

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

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

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

Ведомость

БПМИ231 БПМИ232 БПМИ233 БПМИ234


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

БПМИ231 БПМИ232 БПМИ233 БПМИ234

Книги

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

  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,
Источник — «http://wiki.cs.hse.ru/index.php?title=Теория_чисел_(пилотный_поток)_2023/24&oldid=84391»