Теория чисел

Бакалавриат 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 (без округления), то студент может не сдавать экзамен. В этом случае ИО = Округление(НО). Округление арифметическое. Без уважительной причины студент может сдать только одно ДЗ за семестр после дедлайна (оно оценивается без штрафа), причем сдать такое ДЗ нужно не позднее, чем за две недели до начала зимней сессии (например, это значит, что последнее ДЗ после дедлайна сдать не получится). В случае наличия уважительной причины ситуация решается индивидуально.

Программа дисциплины