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

2026-03-17T19:55:22Z

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

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

== О курсе ==

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

{| class="wikitable" style="text-align:center"
|-
! Группы !! [https://t.me/+vy7YWVCoSf4yNTUy БПМИ256] !! [https://t.me/+rAgJmuox4rMxNTFi БПМИ257] !! [https://t.me/+KnUg2AfcyixhMTli БПМИ258] !! [https://t.me/+1mEij13wcto5YmYy БПМИ259] !! [https://t.me/+21ihkCSMA9U1YWZi БПМИ2510] !! [https://t.me/+3LH9u8c9wNBkNDUy БПМИ2511] !! [https://t.me/+TFP7oiFhnLtjZDg6 БПМИ2512] !! [https://t.me/+48F73Nebm6tlMmFi БПМИ2513] !! [https://t.me/+gm_DrW5tc1diMzMy БПМИ2514] !! [https://t.me/+74-n06A5DFkwOGNi БПМИ2515]
|-
!Лектор ||colspan="10"| [https://t.me/oleg_n_german О.Н. Герман]
|-
!Семинаристы !! [https://t.me/oleg_n_german Герман Олег Николаевич] !! [https://t.me/AlexeyVUstinov Устинов Алексей Владимирович] !! [https://t.me/azapryagaev Запрягаев Александр Александрович] !! [https://t.me/Artyom_Radomskii Радомский Артем Олегович] !! [https://t.me/kyxa_ia Кухарчук Иван Андреевич] !! colspan="2" | [https://t.me/Vitalique_Iudelevich Юделевич Виталий Викторович] !! Чанга Марис Евгеньевич !! [https://t.me/aleksandrov_ki Александров Кирилл Игоревич] !! [https://t.me/DmitryFrolenkov Фроленков Дмитрий Андреевич]
|-
! Ассистенты !! [https://t.me/lizkmrv Комарова Елизавета], [https://t.me/Rimuru_Chiaki Ван Петр] !! [https://t.me/rdctvcake Ли Людмила], [https://t.me/Viu_76 Акбарова Севинч] !! [https://t.me/LewerG Гузаиров Тимур], [https://t.me/akhujamov Худжамов Асадбек] !! [https://t.me/poltorq Босякова Яна], [https://t.me/hilolboboev Бобоев Хилол] !! [https://t.me/Enderka_123 Дмитриев Андрей], [https://t.me/Afrin4ik Мамедов Африн] !! [https://t.me/w_wip Грицан Максим], [https://t.me/parsifal45 Лисиенко Данил] !! [https://t.me/lizkmrv Комарова Елизавета], [https://t.me/Afrin4ik Мамедов Африн] !! [https://t.me/magol13 Головачёва Мария], [https://t.me/alibaba_dushan Бабинский Георгий ] !! [https://t.me/m6sklv Соколов Матвей ], [https://t.me/yungnolife Боженов Ростислав ] !! [https://t.me/pomalkv Маликова Полина], [https://t.me/Windy_Pump Шмыгина Эмилия ]
|-
!Ассистент лектора || colspan="10"| [https://t.me/raspberru Грецкая Вера Ильинична]
|}
<br/>

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

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

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

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

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

== Лекции ==

Лекция 1 (12.01.2026): Деление с остатком, алгоритм Евклида, представление НОД двух чисел в виде их линейной комбинации с целыми коэффициентами. Конечные цепные дроби, рекуррентные соотношения для числителей и знаменателей подходящих дробей, сходимость бесконечной цепной дроби.

Лекция 2 (19.01.2026): Важная лемма (она же обобщённая лемма Евклида), основная теорема арифметики, линейные диофантовы уравнения от двух неизвестных, теорема Ламе о количестве делений с остатком в алгоритме Евклида.

Лекция 3 (26.01.2026): Сравнения по модулю, классы вычетов, критерий обратимости вычета по умножению, теорема Вильсона, теорема о полной и приведённой системах вычетов, теорема Эйлера, малая теорема Ферма.

Лекция 4 (02.02.2026): Криптографическая система RSA, понятие решения полиномиального сравнения, китайская теорема об остатках, количество решений полиномиального сравнения по простому модулю.

Лекция 5 (09.02.2026): Лемма Гензеля и подъём решения, критерий Эйлера квадратичности вычета, определение символа Лежандра.

Лекция 6 (16.02.2026): Элементарные свойства символа Лежандра, лемма Гаусса о символе Лежандра, вывод формулы для символа Лежандра от двойки.

Лекция 7 (21.02.2026): Доказательство квадратичного закона взаимности Гаусса, символ Якоби и его свойства. Тест Соловея-Штрассена.

Лекция 8 (02.03.2026): Доказательство теоремы о тесте Соловея-Штрассена, определение показателя вычета по модулю, делимость значения функции Эйлера на показатель, определение первообразного корня, критерий первообразности.

Лекция 9 (07.03.2026): Мультипликативность функции Эйлера и явная формула для неё, теорема о количестве первообразных корней в приведённой системе вычетов, доказательство существования первообразных корней по простому модулю.

Лекция 10 (16.03.2026): Критерий первообразности, описание модулей, по которым существуют первообразные корни, протокол Диффи-Хеллмана построения общего ключа шифрования, криптографическая система Эль-Гамаля.

[https://disk.yandex.ru/i/xOO5KTVY8W1nHA Конспект лекций 2025-го года]

[https://disk.360.yandex.ru/i/ETzR83Kwy1Rc_A Лекция 02.02.2026]

[https://disk.360.yandex.ru/i/bUITc_UGLAS0lQ Лекция 20.02.2026]

[https://disk.360.yandex.ru/i/avtdB57Q4IAq4A Лекция 06.03.2026]

[https://disk.360.yandex.ru/i/0_tKaU5SldOT-w Конспект лекций 2026-го года]

== Семинары ==

[https://disk.360.yandex.ru/i/Jy4w_XDG01yTiQ Семинар 1]

[https://disk.360.yandex.ru/i/ffCvbhrHH2Q7tA Семинар 2]

[https://disk.360.yandex.ru/i/O8M93uNR_0tyVw Семинар 3]

[https://disk.360.yandex.ru/i/mMiEkzjt_twUQg Семинар 4]

[https://disk.360.yandex.ru/i/BXLchMxGfuxUEQ Семинар 5]

[https://disk.360.yandex.ru/i/_9wU31B8ViFfHQ Семинар 6]

[https://disk.360.yandex.ru/i/lJZDkBxhd6te5w Семинар 7]

[https://disk.360.yandex.ru/i/TqoB5zQaWiH-Rw Семинар 8]

[https://disk.360.yandex.ru/i/-qhqIPHdLd6M6w Семинар 9]

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

[https://disk.360.yandex.ru/i/xcOoS6VQh_jngw ДЗ 1]

[https://disk.360.yandex.ru/i/fLI9romKqeC-4Q ДЗ 2]

[https://disk.360.yandex.ru/i/l84CDb1weUlz9Q ДЗ 3]

[https://disk.360.yandex.ru/i/oOJnRDtxl4kSiQ ДЗ 4]

[https://disk.360.yandex.ru/i/6yLQeeRmI1_eOA ДЗ 5]

[https://disk.360.yandex.ru/i/YSTX5pBDvY3O8w ДЗ 6]

[https://disk.360.yandex.ru/i/LvmImDA7e5IXkg ДЗ 7]

[https://disk.360.yandex.ru/i/YyLEAGPtoz97Vg ДЗ 8]

[https://disk.360.yandex.ru/i/mf0qlG8DDxxInQ ДЗ 9]

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

Контрольная работа будет проведена 21 февраля (в субботу) на первой паре (длительность - одна пара). Разрешается использование (кнопочного) калькулятора. Разрешается принести с собой лист формата А4 с выписанными формулами (не с распечатками лекций, а с отдельными формулами, написанными от руки)

==== Распределение по аудиториям ====
R201 - БПМИ256, БПМИ257, БПМИ258

R306 - БПМИ259, БПМИ2510

R401 - БПМИ2511, БПМИ2512, БПМИ2513

R504 - БПМИ2514, БПМИ2515

[https://disk.360.yandex.ru/i/NIzftb21605p8Q Контрольная работа - демо-версия]

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

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

[https://disk.360.yandex.ru/i/_4Kmtq_krx0Z1w Программа курса]

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

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

Билет будет состоять из следующих частей:
#два определения (по 1 баллу каждое);
#формулировки двух теорем без доказательства (по 1 баллу каждая);
#две теоремы с доказательствами (по 2.5 балла каждое).

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

Всего за билет студент может получить до 9 баллов. После этого проверяющий задаёт дополнительный вопрос по программе курса. Ответ на дополнительный вопрос оценивается в 2 балла. Итоговая оценка равна минимуму из 10 и набранного числа баллов.

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

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

{| class="wikitable" style="text-align:center"
|-
! colspan="2" | 20.03 Аудитория R401
|-
! Группа !! Время
|-
|| БПМИ256 || 11:30
|-
|| БПМИ259 || 13:30
|-
|| БПМИ2514 || 15:00
|-
|| БПМИ2515 || 16:30

|}

{| class="wikitable" style="text-align:center"
|-
! colspan="2" | 21.03 Аудитория R204
|-
! Группа !! Время
|-
|| БПМИ2512 || 15:00
|-
|| БПМИ257 || 16:30
|-
|| БПМИ2513 || 18:00

|}

{| class="wikitable" style="text-align:center"
|-
! colspan="2" | 23.03 Аудитория R305
|-
! Группа !! Время
|-
|| БПМИ2511 || 14:40
|-
|| БПМИ258 || 16:20
|-
|| БПМИ2510 || 17:30
|}

== Экзамен ==

Экзамен будет проведен 30 марта (в понедельник) в 11:00 в письменном формате. Длительность - два часа. Разрешается использование (кнопочного) калькулятора. Разрешается принести с собой лист формата А4 с выписанными формулами (не с распечатками лекций, а с отдельными формулами, написанными от руки)

==== Распределение по аудиториям ====
R201 - БПМИ256, БПМИ257, БПМИ258, БПМИ259

R401 - БПМИ2510, БПМИ2511, БПМИ2512, БПМИ2513

R404 - БПМИ2514, БПМИ2515

[https://disk.360.yandex.ru/i/SZMZaiN4TJymoQ Экзамен - демо-версия]

== Оценка ==

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

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

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

== Ведомость ==
{| class="wikitable" style="text-align:center"
|-
! [https://docs.google.com/spreadsheets/d/18v4Lwp7J7EAXmazYTeypk7LCXYSmGU7BlHpcInSVNBU/edit?gid=229551255#gid=229551255 БПМИ256]||[https://docs.google.com/spreadsheets/d/18v4Lwp7J7EAXmazYTeypk7LCXYSmGU7BlHpcInSVNBU/edit?gid=724726636#gid=724726636 БПМИ257] !! [https://docs.google.com/spreadsheets/d/18v4Lwp7J7EAXmazYTeypk7LCXYSmGU7BlHpcInSVNBU/edit?gid=2049186593#gid=2049186593 БПМИ258] !! [https://docs.google.com/spreadsheets/d/18v4Lwp7J7EAXmazYTeypk7LCXYSmGU7BlHpcInSVNBU/edit?gid=183451133#gid=183451133 БПМИ259] !! [https://docs.google.com/spreadsheets/d/18v4Lwp7J7EAXmazYTeypk7LCXYSmGU7BlHpcInSVNBU/edit?gid=867690546#gid=867690546 БПМИ2510] !![https://docs.google.com/spreadsheets/d/18v4Lwp7J7EAXmazYTeypk7LCXYSmGU7BlHpcInSVNBU/edit?gid=593889813#gid=593889813 БПМИ2511] !! [https://docs.google.com/spreadsheets/d/18v4Lwp7J7EAXmazYTeypk7LCXYSmGU7BlHpcInSVNBU/edit?gid=855095648#gid=855095648 БПМИ2512] !! [https://docs.google.com/spreadsheets/d/18v4Lwp7J7EAXmazYTeypk7LCXYSmGU7BlHpcInSVNBU/edit?gid=466862776#gid=466862776 БПМИ2513] !! [https://docs.google.com/spreadsheets/d/18v4Lwp7J7EAXmazYTeypk7LCXYSmGU7BlHpcInSVNBU/edit?gid=1874066094#gid=1874066094 БПМИ2514] !!
[https://docs.google.com/spreadsheets/d/18v4Lwp7J7EAXmazYTeypk7LCXYSmGU7BlHpcInSVNBU/edit?gid=1027778992#gid=1027778992 БПМИ2515]
|}

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

{| class="wikitable" style="text-align:center"
|-
! [https://docs.google.com/spreadsheets/d/1_MphFXbSiUISXJsLI22JpbIHA-rQ0YE1BLEvLqA3dPw/edit?gid=1989747412#gid=1989747412 БПМИ256]||[https://docs.google.com/spreadsheets/d/1_MphFXbSiUISXJsLI22JpbIHA-rQ0YE1BLEvLqA3dPw/edit?gid=1443467987#gid=1443467987 БПМИ257] !! [https://docs.google.com/spreadsheets/d/1_MphFXbSiUISXJsLI22JpbIHA-rQ0YE1BLEvLqA3dPw/edit?gid=1258458558#gid=1258458558 БПМИ258] !! [https://docs.google.com/spreadsheets/d/1_MphFXbSiUISXJsLI22JpbIHA-rQ0YE1BLEvLqA3dPw/edit?gid=420770853#gid=420770853 БПМИ259] !! [https://docs.google.com/spreadsheets/d/1_MphFXbSiUISXJsLI22JpbIHA-rQ0YE1BLEvLqA3dPw/edit?gid=328306085#gid=328306085 БПМИ2510] !![https://docs.google.com/spreadsheets/d/1_MphFXbSiUISXJsLI22JpbIHA-rQ0YE1BLEvLqA3dPw/edit?gid=651319179#gid=651319179 БПМИ2511] !! [https://docs.google.com/spreadsheets/d/1_MphFXbSiUISXJsLI22JpbIHA-rQ0YE1BLEvLqA3dPw/edit?gid=1802675590#gid=1802675590 БПМИ2512] !! [https://docs.google.com/spreadsheets/d/1_MphFXbSiUISXJsLI22JpbIHA-rQ0YE1BLEvLqA3dPw/edit?gid=5883153#gid=5883153 БПМИ2513] !! [https://docs.google.com/spreadsheets/d/1_MphFXbSiUISXJsLI22JpbIHA-rQ0YE1BLEvLqA3dPw/edit?gid=849197000#gid=849197000 БПМИ2514] !! [https://docs.google.com/spreadsheets/d/1_MphFXbSiUISXJsLI22JpbIHA-rQ0YE1BLEvLqA3dPw/edit?gid=1791336804#gid=1791336804 БПМИ2515]
|}

==Книги==
===Основная литература===
#[http://mmmf.msu.ru/lect/nesterenko/mainnth.pdf Нестеренко Ю. В., Теория чисел]
#[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 Ноден П., Китте К. Алгебраическая алгоритмика]
#[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]

===Дополнительная литература===

# Василенко, О. Н. Теоретико-числовые методы в криптографии МЦНМО, 2003
# Герман, О. Н., Нестеренко, Ю. Теоретико-числовые методы в криптографии 2012
# Глухов М. М., Круглов И.А., Пичкур А.Б., Черёмушкин А.В. Введение в теоретико-числовые методы криптографии Лань, 2011
# Кнут, Д. Е. Искусство программирования для ЭВМ. Том 2: Получисленные алгоритмы ``Вильямс'' , М., Санкт-Петербург, Киев, 2000, 724
# Коблиц Н. Курс теории чисел и криптографии. М.: ТВП, 2001.
# Ноден, П., Китте, К. Алгебраическая алгоритмика. Изд-во Мир, Москва, 1999
# Ященко, В. В. (Ed.) Введение в криптографию, МЦНМО, Москва, 1999
# Hoffstein, J.; Pipher, J., Silverman, J. H. An introduction to mathematical cryptography Springer, 2008,

Теория чисел (основной поток) 2025/26 - История изменений

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