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

Бакалавриат 2024/2025

Статус: Курс по выбору (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

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

Где читается: Факультет компьютерных наук

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

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Бельдиев Иван Сергеевич, Калмынин Александр Борисович, Ожегов Фёдор Юрьевич, Устинов Алексей Владимирович

Язык: русский

Кредиты: 3

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

Аннотация

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

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

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

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

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

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

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

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

Домашние задания
Выдаются после каждого семинара по соответствующей теме
Контрольная работа
Планируется провести в середине 3-го модуля.
Коллоквиум
Один коллоквиум по теоретическому материалу.
Экзамен
Экзамен письменный. Билет включает в себя 6-8 задач. Во время подготовки использовать любые материалы запрещается.

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

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

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

Авторы

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

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