Number Theory (advanced course)

2024/2025

Academic Year

RUS

Instruction in Russian

3

ECTS credits

Delivered at:

Big Data and Information Retrieval School

Course type:

Elective course

When:

1 year, 3 module

Instructors

Kalmynin, Alexander B.

Ustinov, Alexey

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

Аннотация

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

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

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

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

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

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

• Алгоритм Евклида.
• Мультипликативные функции.
• Ряды Дирихле. Группы, кольца и поля.
• Теория сравнений.
• Тест простоты. Криптосистема RSA.
• Первообразные корни.
• Криптосистемы Диффи – Хеллмана и Эль Гамаля.
• Криптографические приложения квадратичных вычетов.
• Различные криптосистемы, основанные на теоретико-числовых структурах.
• Умножение Карацубы. Быстрое преобразование Фурье.

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

• Домашние задания
  Обычно домашнее задание выдается к каждому семинару.
• Контрольная работа
  Планируется провести в середине 3-го модуля.
• Коллоквиум
  Планируется провести в конце 3-го модуля.
• Экзамен

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

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

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

Рекомендуемая основная литература

• 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
• Винберг, Э. Б. Курс алгебры : учебник / Э. Б. Винберг. — 5-е изд., стереотип. — Москва : МЦНМО, 2021. — 590 с. — ISBN 978-5-4439-2183-9. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/267500 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Виноградов, И. М.  Основы теории чисел / И. М. Виноградов. — Москва : Издательство Юрайт, 2022. — 123 с. — (Антология мысли). — ISBN 978-5-534-12085-1. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/493846 (дата обращения: 27.08.2024).
• Теория чисел, Бухштаб, А. А., 2008

Рекомендуемая дополнительная литература

• 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). — Режим доступа: для авториз. пользователей.

Авторы

• Кононова Елизавета Дмитриевна
• Сысоева Алевтина Александровна