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

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

О курсе

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

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

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

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

Канал в telegram=?

Семинары

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) Тест "Ферма". Числа Кармайкла. Китайская теорема об остатках (два доказательства). Группы, кольца, поля. Кольцо вычетов. Группа обратимых элементов кольца вычетов.


ВНИМАНИЕ, перенос занятий. Лекция 5 состоится в пятницу 03.02 в 9:30, в R304. На следующей неделе (6-11 февраля) лекций и семинаров по ТЧ НЕ БУДЕТ. О датах перенесённых семинаров сообщим отдельно.

Видеозаписи

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

Семинары

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

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

ДЗ-1 ДЗ-2 ДЗ-3 ДЗ-4

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

Будет проведена одна контрольная работа (ориентировочно) после 6-го занятия.

Экзамен

Оценка

Итог = 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. Ященко, В. В. (Ed.) Введение в криптографию, МЦНМО, Москва, 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=76328»