Теория чисел (пилотный поток) 2024/25

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

О курсе

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


Преподаватели и учебные ассистенты

Группа БПМИ241 БПМИ242 БПМИ243 БПМИ244 БПМИ245
Лектор А.В. Устинов
Семинарист Ожегов Фёдор Юрьевич А.В. Устинов А. Калмынин Бельдиев Иван Сергеевич
Ассистент Заварин Александр Сергеевич Лейла Мурсманидзе Горбач Елизавета Леонидовн Заварин Александр Сергеевич Грецкая Вера Ильинична
Ассистент лектора Агаев Мурад

Лекции

Конспект лекций 1-6.

Лекция 1 (10.01.2025) Основная теорема арифметики. Сравнения и их свойства. Полная и приведённая системы вычетов. Определение группы. Примеры групп. Определение кольца. Примеры колец. Кольцо вычетов. Группа обратимых элементов кольца вычетов. Малая теорема Ферма и теорема Эйлера. Теорема Вильсона.

Лекция 2 (17.01.2025) Мультипликативные функции. Мультипликативность функции Эйлера. Тест "Ферма". Псевдопростые числа. Числа Кармайкла. Тест сильной псевдопростоты. Теорема Рабина (без доказательства). Криптосистема RSA. Электронная подпись RSA.

Лекция 3 (24.01.2025) Асимметричная криптография. Гомоморфное шифрование. Слепая подпись RSA. Забывчивая передача RSA. Китайская теорема об остатках (КТО), три доказательства. Изоморфизмы групп и колец. Прямое произведение групп и колец. КТО как изоморфизм колец вычетов.

Лекция 4 (31.01.2025) Делители нуля. Деление многочленов с остатком. Теорема Безу. Теорема о числе корней многочлена над полем. Расширенный алгоритм Евклида для многочленов. НОД многочленов. Однозначность разложения многочлена в произведение неприводимых. КТО для многочленов. Связь с интерполяционным многочленом Лагранжа. Циклические группы.

Лекция 5 (07.02.2025) Первообразные корни (ПК). Критерий ПК. Существование ПК по простому модулю. Существование ПК по модулю p^2. Существование ПК по модулю p^a. Существование ПК по модулю 2p^a.

Лекция 6 (13.02.2025, вместо 14.02.2025) Индексы. Задача дискретного логарифмирования. Протокол Диффи~--- Хеллмана. Вычислительная задача Диффи~--- Хеллмана. Протокол Эль-Гамаля. Полиномиально сводимые и вычислительно эквивалентные функции. Вычислительная эквивалентность задач DH и EG. Трёхэтапный протокол Шамира. Квадратичные вычеты. Критерий Эйлера. Символ Лежандра. Простейшие свойства символа Лежандра. Критерий Гаусса.

Лекция 7 (21.02.2025)

Лекция 8 (28.02.2025)

Лекция 9 (07.03.2025)

Лекция 10 (14.03.2025)

Семинары и домашние задания

Семинар 1, Семинар 2, Семинар 3, Семинар 4, Семинар 5, Семинар 6


ДЗ-1, ДЗ-2, ДЗ-3, ДЗ-4, ДЗ-5, ДЗ-6


Правила выставления оценок

В домашнем задании каждая задача оценивается в 10 баллов. Баллы за задачи суммируются и линейно шкалируются на 10-балльную шкалу без округления. Итоговая оценка за ДЗ получается усреднением оценок по всем ДЗ (без округления). Округление происходит только в конце при вычислении итоговой оценки за курс.

Правила сдачи заданий

Всё должно быть написано аккуратно и понятно. Ассистент имеет право вызвать студента на защиту задания, если решение неясное или есть подозрение на списывание или использование ИИ. В случае неявки или невозможности объяснить решение студент получает 0 баллов.

ПРОСРОЧКА: У Вас есть возможность дважды отправить домашнее задание после истечения срока сдачи в течение 24 часов. Однако этот шанс не может быть использован для сдачи последнего домашнего задания.

Контрольная работа

21 февраля 18:10-19:30. Аудитории R201, R204. Темы: теоремы Ферма, Эйлера, Вильсона; псевдопростые числа; числа Кармайкла; китайская теорема об остатках для чисел и многочленов; первобразные корни и индексы.

Демо-вариант

Дистанционное участие возможно для тех, у кого есть уважительная причина, подтверждённая учебным офисом (болезнь, дистанционное обучение, участие в важной олимпиаде). Перед экзаменом преподаватели должны иметь подтверждение из учебного офиса, что у студента есть уважительная причина.

Правила контрольной работы

1. Допускается использование листа формата А4 для записей, однако писать разрешается только на одной его стороне.

2. Разрешается принести с собой калькулятор.

3. Можно от руки написать на планшете и затем распечатать.


Коллоквиум

21 марта с 9:30 до 16:00, аудитория R205.


Экзамен

Экзамен письменный, 26 марта 2025 г. Длительность 2.5 часа, начало в 13:00, аудитории R201, R305.

Оценка

В течение года установлены следующие формы контроля:

  • один письменный экзамен (ЭК), в сессию после модуля;
  • одна письменная контрольная работа (KР), которую планируется провести в середине 3-го модуля;
  • один коллоквиум (KЛ), который планируется провести в конце 3-го модуля;
  • около 10 домашних заданий (ДЗ, где ДЗ --- есть среднее арифметическое оценок всех домашних работ); обычно домашнее задание выдается к каждому семинару.

Накопленная Оценка, НО, вычисляется без округления по следующей формуле: НО = 0.4 * ДЗ + 0.2 * Кр + 0.4 * КЛ. Итоговая Оценка за Курс, ИО, вычисляется по следующей формуле: ИО = Округление(7/10*НО + 3/10*ЭК),

где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, ЭК — оценка за экзамен, КЛ — оценка за коллоквиум. Если НО не меньше 8 (без округления), то студент может не сдавать экзамен. В этом случае ИО = Округление(НО). Округление арифметическое.

Ведомость

БПМИ241 БПМИ242 БПМИ243 БПМИ244

БПМИ245

Сводная таблица с оценками по ДЗ

БПМИ241 БПМИ242 БПМИ243 БПМИ244

БПМИ245

Полезные ссылки

Конспект лекций 2023 года.

Теория чисел (пилотный поток) 2023/24

Криптография на решётках 23/24 (факультатив, будет читаться и в 4-м модуле 24/25 у.г.)

Дополнительные главы теории чисел (факультатив в 4-м модуле 22/23 у.г.)

Книги

Основная литература

  1. [АР] Айерленд К. Роузен, М. Классическое введение в современную теорию чисел. - М.: Мир, 1998.
  2. [A] Акритас А.Г. Основы компьютерной алгебры с приложениями. 1994
  3. [АУ] Алфутова Н. Б., Устинов А. В. Алгебра и теория чисел. Сборник задач для математических школ. М.: МЦНМО, 2018
  4. [Б] Бухштаб А. А., Теория чисел
  5. [ВИМ] Виноградов И. М., Основы теории чисел.
  6. [НК] Ноден П., Китте К. Алгебраическая алгоритмика
  7. [MOV] Menezes A., Oorschot P. van, Vanstone S. Handbook of Applied Cryptography

Дополнительная литература

  1. Василенко, О. Н. Теоретико-числовые методы в криптографии МЦНМО, 2003
  2. [ВЭБ] Винберг Э. Б. Курс алгебры
  3. Герман, О. Н., Нестеренко, Ю. Теоретико-числовые методы в криптографии 2012
  4. Гашков С. Б., Применко Э. А., Черепнев М. А. Криптографические методы защиты информации, Академия, 2010
  5. Глухов М. М., Круглов И.А., Пичкур А.Б., Черёмушкин А.В. Введение в теоретико-числовые методы криптографии Лань, 2011
  6. Кнут, Д. Е. Искусство программирования для ЭВМ. Том 2: Получисленные алгоритмы "Вильямс" , М., Санкт-Петербург, Киев, 2000
  7. Коблиц Н. Курс теории чисел и криптографии. М.: ТВП, 2001.
  8. Нестеренко Ю. В., Теория чисел
  9. Ященко, В. В. (ред.) Введение в криптографию, МЦНМО, Москва, 1999
  10. Hoffstein, J.; Pipher, J., Silverman, J. H. An introduction to mathematical cryptography Springer, 2008,
Источник — «http://wiki.cs.hse.ru/index.php?title=Теория_чисел_(пилотный_поток)_2024/25&oldid=89739»