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

2025-03-30T18:23:53Z

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

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

== О курсе ==

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

=== Преподаватели и учебные ассистенты ===
{| class="wikitable" style="text-align:center"
|-
! Группа !! [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="5"| [https://t.me/AlexeyVUstinov А.В. Устинов]
|-
|| Семинарист || Ожегов Фёдор Юрьевич || [https://t.me/AlexeyVUstinov А.В. Устинов] ||colspan="2" | А. Калмынин || Бельдиев Иван Сергеевич
|-
|| Ассистент || [https://t.me/wa731 Заварин Александр Сергеевич ] || [https://t.me/jtqjd0 Лейла Мурсманидзе] || [https://t.me/lizgbet Горбач Елизавета Леонидовн] || [https://t.me/wa731 Заварин Александр Сергеевич ] || [https://t.me/raspberru Грецкая Вера Ильинична]
|-
|| Ассистент лектора || colspan="5" | [https://t.me/citizen_murad Агаев Мурад]
|-
|}

== Лекции ==

[https://drive.google.com/file/d/13DtZf1COOZu0ndryxoW6zKi7VXuN1D6L/view?usp=sharing Конспект лекций.]

Лекция 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) Вероятностное шифрование. Криптосистема Пэйе.

== Семинары и домашние задания ==
[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]

[https://drive.google.com/file/d/1M8WTigV8mbamxMNg9H0eHlRF6Zdh84IL/view?usp=sharing ДЗ 10 (на каникулы)]

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

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

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

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

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

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

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

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

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

[https://drive.google.com/file/d/1pUBEbmrBlFE81Qt3Gtzdf7DKqflG0BZL/view?usp=sharing Демо-вариант]

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

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

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

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

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

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



== Коллоквиум ==
=== Расписание коллоквиума ===
Коллоквиум состоится 21-го марта.
{| class="wikitable" style="text-align:center"
|-
! Группа !! Время !! аудитория
|-
||9:30 || БПМИ244 || R204
|-
||11:30 || БПМИ243 || R204
|-
||9:30 || БПМИ245 || R205
|-
||11:30 || БПМИ241 || R205
|-
||13:30 || БПМИ242 || R205
|}

[https://drive.google.com/file/d/1o8El78SejNH3XXChgeBRUhR-2-5hAPFy/view?usp=sharing Программа коллоквиума]

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

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

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



== Экзамен ==

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

[https://drive.google.com/file/d/16sPt9nOa4Gy6-uCL3pD5ZmCPHlvwyDJy/view?usp=sharing Демо-версия]

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

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



[https://us06web.zoom.us/j/81169938145?pwd=6nhsz2OpNbxHbACSplkYDRbblnLLBa.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/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]
|}

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

{| class="wikitable" style="text-align:center"
|-
! [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 у.г.)

==Книги==
===Основная литература===
# [АР] [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
# Гашков С. Б., Применко Э. А., Черепнев М. А. Криптографические методы защиты информации, Академия, 2010
# Глухов М. М., Круглов И.А., Пичкур А.Б., Черёмушкин А.В. Введение в теоретико-числовые методы криптографии Лань, 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,

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

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