Теория чисел (углубленный курс)

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

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