Кто читает:: Департамент больших данных и информационного поиска

Статус:: Курс по выбору

Когда читается:: 1-й курс, 3 модуль

Преподаватели

Калмынин Александр Борисович

Ожегов Фёдор Юрьевич

Устинов Алексей Владимирович

Полная версия программы учебной дисциплины

Аннотация

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

Цель освоения дисциплины

Знать базовые теоретико-числовые алгоритмы. Уметь оценивать их сложность.
Знать основные результаты теории сравнений (малая теорема Ферма, теорема Эйлера, китайская теорема об остатках). Знать свойства квадратичных вычетов и первообразных корней.
Знать базовые криптографические протоколы, основанные на теоретико-числовых структурах.

Планируемые результаты обучения

Знать свойства первообразных корней и дискретных логарифмов.
Уметь доказывать корректность работы базовых криптографичеких протоколов и обосновывать их стойкость.
Знание основ теории чисел.
Умение доказывать корректность работы базовых криптографичеких протоколов и обосновывать их стойкость.

Содержание учебной дисциплины

Алгоритмы и их сложность. Классические алгоритмы целочисленной арифметики. Алгоритм Евклида.
Уравнение ax+by=c. Основная теорема арифметики. Мультипликативные функции. Формула обращения Мёбиуса.
Сравнения. Теоремы Вильсона, Ферма и Эйлера. Функция Эйлера.
Криптосистема RSA. Односторонние функции. Китайская теорема об остатках. Решение систем линейных сравнений.
Теорема о числе корней многочлена над полем. Тесты простоты. Псевдопростые числа. Схема разделения секрета Шамира.
Квадратичные вычеты. Свойства символов Лежандра и Якоби. Квадратичный закон взаимности.
Первообразные корни и индексы.
Тест Соловея – Штрассена. Псевдопростые числа Эйлера. Криптосистема Рабина. Криптографические протоколы, использующие свойства символа Якоби.
Задача дискретного логарифмирования. Протокол Диффи-Хеллмана. Криптосистема Эль-Гамаля. Протоколы аутентификации и «подбрасывание монеты по Телефону». Гомоморфное шифрование.
Умножение Карацубы. Быстрое преобразование Фурье.

Элементы контроля

Домашние задания
Контрольная работа
Коллоквиум
Экзамен

Промежуточная аттестация

2023/2024 учебный год 3 модуль
В течение года установлены следующие формы контроля: один письменный экзамен (ЭК), в сессию после модуля;· одна письменная контрольная работа (KР), которую планируется провести в середине 3-го модуля;· один коллоквиум (KЛ), который планируется провести в конце 3-го модуля; · около 10 домашних заданий (ДЗ, где ДЗ --- есть среднее арифметическое оценок всех домашних работ); обычно домашнее задание выдается к каждому семинару. Накопленная Оценка, НО, вычисляется без округления по следующей формуле: НО = 0.4 * ДЗ + 0.2 * Кр + 0.4 * КЛ. Итоговая Оценка за Курс, ИО, вычисляется по следующей формуле: ИО = Округление(7/10*НО + 3/10*ЭК), где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, ЭК — оценка за экзамен, КЛ – оценка за коллоквиум. Если НО не меньше 8 (без округления), то студент может не сдавать экзамен. В этом случае ИО = Округление(НО). Округление арифметическое. Без уважительной причины студент может сдать только одно ДЗ за семестр после дедлайна (оно оценивается без штрафа), причем сдать такое ДЗ нужно не позднее, чем за две недели до начала зимней сессии (например, это значит, что последнее ДЗ после дедлайна сдать не получится). В случае наличия уважительной причины ситуация решается индивидуально.

Список литературы

Авторы

Кононова Елизавета Дмитриевна

Бакалаврская программа «Прикладная математика и информатика»

Менеджер

По вопросам поступления консультирует

Адрес

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

Преподаватели

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