We use cookies in order to improve the quality and usability of the HSE website. More information about the use of cookies is available here, and the regulations on processing personal data can be found here. By continuing to use the site, you hereby confirm that you have been informed of the use of cookies by the HSE website and agree with our rules for processing personal data. You may disable cookies in your browser settings.

  • A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Number Theory (advanced course)

2024/2025
Academic Year
RUS
Instruction in Russian
3
ECTS credits
Course type:
Elective course
When:
1 year, 3 module

Instructors


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

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

Аннотация

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

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

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

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

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

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

  • Алгоритм Евклида.
  • Мультипликативные функции.
  • Ряды Дирихле. Группы, кольца и поля.
  • Теория сравнений.
  • Тест простоты. Криптосистема 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). — Режим доступа: для авториз. пользователей.

Авторы

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