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

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

О курсе

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

Предварительная программа

  1. Алгоритмы и их сложность. Классические алгоритмы целочисленной арифметики. Быстрый алгоритм возведения в степень.
  2. Алгоритм Евклида и его варианты. Теорема Ламе. Расширенный алгоритм Евклида.
  3. Конечные цепные дроби. Свойства подходящих дробей.
  4. Бесконечные цепные дроби. Однозначность представления действительных чисел цепными дробями. Теорема Лагранжа.
  5. Теория сравнений. Кольцо вычетов. Группа обратимых кольца вычетов. Теорема Вильсона. Функция Эйлера. Теоремы Ферма и Эйлера. [Простейшие детерминированные и вероятностные тесты на простоту. Псевдопростые, абсолютно псевдопростые и сильно псевдопростые числа. Понятие о криптографии с открытым ключом. Система шифрования RSA. Криптосистема Эль-Гамаля.]
  6. Китайская теорема об остатках. Решение систем линейных сравнений. Решение полиномиальных сравнений. [Криптосистема Рабина и её модификации. ]
  7. Квадратичные вычеты. Свойства символов Лежандра и Якоби. Квадратичный закон взаимности. [Тест Соловея--Штрассена. Псевдопростые числа Эйлера. Протоколы, использующие свойства символа Якоби. Генератор Блюм -- Блюма -- Шуба. Криптосистема Блюма -- Гольдвассер. Криптосистема Гольдвассер -- Микали.]
  8. Первообразные корни и индексы. Структура группы $\mathbb{Z}^*_m$ для произвольного $m$ [Метод Диффи-Хеллмана. Дискретное логарифмирование. Протоколы аутентификации и "подбрасывание монеты по телефону". Хеш-функция Шаума -- Хайста -- Пфитсман.]
  9. Интерполяционный многочлен Лагранжа и его связь с китайской теоремой об остатках. Умножение Карацубы. [Разделение секрета Шамира.]
  10. Дискретное преобразование Фурье. Быстрое преобразование Фурье.

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

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

Семинары

221, 222 -- Устинов Алексей Владимирович, 223, 224 -- Калмынин Александр Борисович.

Ассистенты

221 - Свирщевский Юрий, 222 - Шевченко Пётр, 223 - Кучерявый Пётр, 224 - Пичушкин Антон.

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

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

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

Всё должно быть написано аккуратно и понятно.

Лекции

Лекция 1 (12.01.2023) Сложность алгоритмов. Алгоритм Евклида. Теорема Ламе. Расширенный алгоритм Евклида. [A]

Лекция 2 (19.01.2023) Основная теорема арифметики. Уравнение ax+by=c. Цепные дроби. Представление рациональных чисел конечными цепными дробями. Рекуррентные соотношения на числители и знаменатели подходящих дробей. [Б, ВИМ,Х]

Лекция 3 (26.01.2023) Свойства подходящих дробей. Бесконечные цепные дроби. Приближение чисел подходящими дробями. Теорема Лежандра (критерий подходящей дроби).[Б, ВИМ, Х]

Лекция 4 (02.02.2023) Теорема Лежандра (критерий подходящей дроби). Сравнения и их свойства. Полная и приведённая системы вычетов. Функция Эйлера. Теорема Эйлера. Малая теорема Ферма. Псевдопростые числа Ферма.

Лекция 5 (03.02.2023) Тест "Ферма". Числа Кармайкла. Китайская теорема об остатках (два доказательства). Группы, кольца, поля. Кольцо вычетов. Группа обратимых элементов кольца вычетов. [ВЭБ]

Лекция 6 (16.02.2023) Теорема о числе корней многочлена над полем. Теорема Вильсона. Тест сильной псевдопростоты. Изоморфизм групп. Изоморфизм колец. Прямое произведение групп. Прямое произведение колец. Китайская теорема об остатках как изоморфизм колец. Мультипликативность функции Эйлера. Формула для вычисления функции Эйлера. [НК]

(23.02.2023) Лекция пропала из-за праздника.

Лекция 7 (02.03.2023) RSA, шифрование + ЭЦП. Понятие о криптографии с открытым ключом. [MOV] Подгруппы. Теорема Лагранжа о порядке подгруппы. Циклические группы. [ВЭБ]

Лекция 8 (09.03.2023) Следствия теоремы Лагранжа. Первообразные корни (ПК). Критерий ПК. Индексы и их свойства. Криптосистемы Диффи -- Хеллмана и Эль Гамаля. Квадратичные вычеты. Критерий Эйлера.

Лекция 9 (16.03.2023) Символ Лежандра. Простейшие свойства символа Лежандра. Квадратичный закон взаимности. Символ Якоби.

Лекция 10 (17.03.2023) Свойства символа Якоби. Псевдопростые числа Эйлера. Тест Соловея -- Штрассена. Протоколы привязки к биту. Привязка к биту Гольдвассер -- Микали. Шифрование Гольдвассер -- Микали. Криптосистема Гольдвассер -- Микали как криптосистема гомоморфного шифрования.

Видеозаписи

Конспект лекций (будет дорабатываться)

Семинары

Семинар 1, Семинар 2, Семинар 3, Семинар 4, Семинар 5, Семинар 6, Семинар 7, Семинар 8, Семинар 9, Семинар 10

Домашние задания

ДЗ-1 ДЗ-2 ДЗ-3 ДЗ-4 ДЗ-5 ДЗ-6 ДЗ-7 ДЗ-8 ДЗ-9

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

Контрольная работа 4 марта (суббота) в 9:30, длительность - 1:20.

Аудитории R201 (240 чел.), R205 (122 чел.), R301 (240 чел.), R304 (192 чел.), R404 (192 чел.), R405 (122 чел.), R503 (112 чел.).

Контрольная - обобщённый модельный вариант

В контрольную 4 марта войдут 7 задач указанных типов.

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

Экзамен

Экзамен письменный, 2.5 часа. Билеты к экзамену (с баллами). Модельные задачи в последнем билете.

Оценка

Итог = min(10, Округление(0.25 * ДЗ + 0.25 * КР + 0.5 * Э)), где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, Э — оценка за экзамен. Округление арифметическое.


Книги

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

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

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

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