Бакалавриат
2023/2024
Теория чисел
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 3 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
3
Контактные часы:
40
Программа дисциплины
Аннотация
С одной стороны, в курсе будут излагаться основы теории чисел: алгоритм Евклида, арифметические функции, теория сравнений, квадратичные вычеты, первообразные корни. С другой стороны, параллельно будет происходить знакомство с приложениями теории чисел в криптографии и простейшими криптографическими протоколами.
Цель освоения дисциплины
- Знать базовые алгоритмы целочисленной арифметики. Уметь оценивать их сложность.
- Знать основные результаты теории сравнений (малая теорема Ферма, теорема Эйлера, китайская теорема об остатках).
- Знать свойства квадратичных вычетов.
Планируемые результаты обучения
- Знать базовые алгоритмы целочисленной арифметики. Уметь оценивать их сложность.
- Знать свойства первообразных корней и дискретных логарифмов.
- Уметь доказывать корректность работы базовых криптографичеких протоколов и обосновывать их стойкость.
Содержание учебной дисциплины
- Алгоритмы и их сложность. Классические алгоритмы целочисленной арифметики. Алгоритм Евклида.
- Уравнение ax+by=c. Основная теорема арифметики. Цепные дроби.
- Мультипликативные функции. Формула обращения Мёбиуса.
- Сравнения. Теоремы Вильсона, Ферма и Эйлера. Функция Эйлера.
- Криптосистема RSA. Односторонние функции. Китайская теорема об остатках. Решение систем линейных сравнений.
- Теорема о числе решений полиномиального сравнения по простому модулю. Тесты простоты. Псевдопростые числа.
- Квадратичные вычеты. Свойства символов Лежандра и Якоби. Квадратичный закон взаимности.
- Тест Соловея–Штрассена. Псевдопростые числа Эйлера. Криптографические протоколы, использующие свойства символа Якоби.
- Первообразные корни и индексы.
- Задача дискретного логарифмирования. Протокол Диффи-Хеллмана. Криптосистема Эль-Гамаля.
Элементы контроля
- Домашние заданияВыдаются после каждого семинара по соответствующей теме
- Контрольная работа
- Коллоквиум
- Экзамен
Промежуточная аттестация
- 2023/2024 учебный год 3 модульВ течение года установлены следующие формы контроля: один письменный экзамен (ЭК), в сессию после модуля;· одна письменная контрольная работа (KР), которую планируется провести в середине 3-го модуля;· один коллоквиум (KЛ), который планируется провести в конце 3-го модуля; · около 10 домашних заданий (ДЗ, где ДЗ --- есть среднее арифметическое оценок всех домашних работ); обычно домашнее задание выдается к каждому семинару. Накопленная Оценка, НО, вычисляется без округления по следующей формуле: НО = 0.4 * ДЗ + 0.2 * Кр + 0.4 * КЛ. Итоговая Оценка за Курс, ИО, вычисляется по следующей формуле: ИО = Округление(7/10*НО + 3/10*ЭК), где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, ЭК — оценка за экзамен, КЛ – оценка за коллоквиум. Если НО не меньше 8 (без округления), то студент может не сдавать экзамен. В этом случае ИО = Округление(НО). Округление арифметическое. Без уважительной причины студент может сдать только одно ДЗ за семестр после дедлайна (оно оценивается без штрафа), причем сдать такое ДЗ нужно не позднее, чем за две недели до начала зимней сессии (например, это значит, что последнее ДЗ после дедлайна сдать не получится). В случае наличия уважительной причины ситуация решается индивидуально.
Список литературы
Рекомендуемая основная литература
- Alfred J. Menezes, Paul C. van Oorschot, & Scott A. Vanstone. (1997). Handbook of Applied Cryptography. CRC Press.
- Алфутова, Н. Б. Алгебра и теория чисел. Сборник задач для математических школ : учебное пособие / Н. Б. Алфутова, А. В. Устинов. — 3-е изд. доп. и испр. — Москва : МЦНМО, 2009. — 336 с. — ISBN 978-5-94057-550-4. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9279 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Введение в криптографию, Ященко, В. В., 2012
- Виноградов, И. М. Основы теории чисел / И. М. Виноградов. — Москва : Издательство Юрайт, 2023. — 123 с. — (Антология мысли). — ISBN 978-5-534-12085-1. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/516109 (дата обращения: 27.08.2024).
- Теория чисел, Бухштаб, А. А., 1966
Рекомендуемая дополнительная литература
- J.H. Silverman, Jill Pipher, Jeffrey Hoffstein. An Introduction to Mathematical Cryptography. Springer-Verlag New York 2008
- Введение в теоретико-числовые методы криптографии : учебное пособие / М. М. Глухов, И. А. Круглов, А. Б. Пичкур, А. В. Черемушкин. — Санкт-Петербург : Лань, 2022. — 400 с. — ISBN 978-5-8114-1116-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/210746 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Искусство программирования для ЭВМ, Кнут, Д., 1976-1978