imported>Ustinov: Migrated current public revision from wiki.cs.hse.ru

2024-03-28T21:05:58Z

Migrated current public revision from wiki.cs.hse.ru

Новая страница

== О курсе ==

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

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

[[Дополнительные главы теории чисел]] (курс в 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 Агаев Мурад]
|-
|}

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

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

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

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

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

== Лекции ==

[https://drive.google.com/file/d/1gSAJGCRom_DFr2rho0uzVLtPpVE8NTOi/view?usp=sharing Конспект лекций прошлого года.]

Лекция 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, Рабин, Гольдвассер -- Микали).

== Семинары ==
[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] 

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

[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/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.

==== Распределение по аудиториям ====
R401 - БПМИ231, БПМИ234

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

[https://drive.google.com/file/d/1T_llw5UMgtlIauw3uPtFONwwBpdPb8Yk/view?usp=sharing Модельный вариант]

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

[https://us06web.zoom.us/j/81522212645?pwd=mlNMksCHuzArr8v062S5BJluRGRolJ.1 Ссылка] для тех, кто будет онлайн сдавать.

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

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

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

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



== Коллоквиум ==

[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 за коллоквиум без возможности пересдачи.

== Экзамен ==

Экзамен письменный, 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сылка] для тех, кто будет онлайн сдавать.

== Оценка ==

В течение года установлены следующие формы контроля:
* один письменный экзамен (ЭК), в сессию после модуля;
* одна письменная контрольная работа (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]
# [АУ] [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 Ноден П., Китте К. Алгебраическая алгоритмика]
# [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]
# [ВЭБ] [https://mathprofi.com/uploads/files/2581_f_41_e.b.vinberg-kurs-algebry-2-e-izd.pdf Винберг Э. Б. Курс алгебры]
# Герман, О. Н., Нестеренко, Ю. Теоретико-числовые методы в криптографии 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,

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

imported>Ustinov: Migrated current public revision from wiki.cs.hse.ru