Теория чисел (пилотный поток) 2022/23 — различия между версиями
Ustinov (обсуждение | вклад) |
Ustinov (обсуждение | вклад) |
||
Строка 51: | Строка 51: | ||
== Лекции == | == Лекции == | ||
− | Лекция 1 (12.01.2023) Алгоритм Евклида. Теорема Ламе. Расширенный алгоритм Евклида. | + | Лекция 1 (12.01.2023) Сложность алгоритмов. Алгоритм Евклида. Теорема Ламе. Расширенный алгоритм Евклида. [A] |
− | Лекция 2 (19.01.2023) Основная теорема арифметики. Уравнение ax+by=c. Цепные дроби. Представление рациональных чисел конечными цепными дробями. Рекуррентные соотношения на числители и знаменатели подходящих дробей. | + | Лекция 2 (19.01.2023) Основная теорема арифметики. Уравнение ax+by=c. Цепные дроби. Представление рациональных чисел конечными цепными дробями. Рекуррентные соотношения на числители и знаменатели подходящих дробей. [Б, ВИМ] |
− | Лекция 3 (26.01.2023) Свойства подходящих дробей. Бесконечные цепные дроби. Приближение чисел подходящими дробями. Теорема Лежандра (критерий подходящей дроби). О приближениях подходящими дробями золотого сечения. Теорема Маркова -- Гурвица. | + | Лекция 3 (26.01.2023) Свойства подходящих дробей. Бесконечные цепные дроби. Приближение чисел подходящими дробями. Теорема Лежандра (критерий подходящей дроби). О приближениях подходящими дробями золотого сечения. Теорема Маркова -- Гурвица. [АУ, Б, ВИМ] |
[https://drive.google.com/file/d/1o7hJFz11Cf9fTfes2iz3ddZLetw34ufZ/view?usp=sharing Конспект лекций 1-2] | [https://drive.google.com/file/d/1o7hJFz11Cf9fTfes2iz3ddZLetw34ufZ/view?usp=sharing Конспект лекций 1-2] |
Версия 15:33, 24 января 2023
Содержание
О курсе
Это курс основ теории чисел, который содержит такие базовые разделы как алгоритм Евклида, цепные дроби, арифметические функции, теория сравнений, квадратичные вычеты, первообразные корни. Параллельно будет происходить знакомство с задачами математической криптографии и простейшими криптографическими протоколами.
Предварительная программа
- Алгоритмы и их сложность. Классические алгоритмы целочисленной арифметики. Быстрый алгоритм возведения в степень.
- Алгоритм Евклида и его варианты. Теорема Ламе. Расширенный алгоритм Евклида.
- Конечные цепные дроби. Свойства подходящих дробей.
- Бесконечные цепные дроби. Однозначность представления действительных чисел цепными дробями. Теорема Лагранжа.
- Теория сравнений. Кольцо вычетов. Группа обратимых кольца вычетов. Теорема Вильсона. Функция Эйлера. Теоремы Ферма и Эйлера. [Простейшие детерминированные и вероятностные тесты на простоту. Псевдопростые, абсолютно псевдопростые и сильно псевдопростые числа. Понятие о криптографии с открытым ключом. Система шифрования RSA. Криптосистема Эль-Гамаля.]
- Китайская теорема об остатках. Решение систем линейных сравнений. Решение полиномиальных сравнений. [Криптосистема Рабина и её модификации. ]
- Квадратичные вычеты. Свойства символов Лежандра и Якоби. Квадратичный закон взаимности. [Тест Соловея--Штрассена. Псевдопростые числа Эйлера. Протоколы, использующие свойства символа Якоби. Генератор Блюм -- Блюма -- Шуба. Криптосистема Блюма -- Гольдвассер. Криптосистема Гольдвассер -- Микали.]
- Первообразные корни и индексы. Структура группы $\mathbb{Z}^*_m$ для произвольного $m$ [Метод Диффи-Хеллмана. Дискретное логарифмирование. Протоколы аутентификации и "подбрасывание монеты по телефону". Хеш-функция Шаума -- Хайста -- Пфитсман.]
- Интерполяционный многочлен Лагранжа и его связь с китайской теоремой об остатках. Умножение Карацубы. [Разделение секрета Шамира.]
- Дискретное преобразование Фурье. Быстрое преобразование Фурье.
Полезные ссылки
Почта для сдачи домашних заданий
Канал в telegram для объявлений: Чат в telegram для обсуждений: Ссылка на курс в Anytask:
Семинары
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) Свойства подходящих дробей. Бесконечные цепные дроби. Приближение чисел подходящими дробями. Теорема Лежандра (критерий подходящей дроби). О приближениях подходящими дробями золотого сечения. Теорема Маркова -- Гурвица. [АУ, Б, ВИМ]
Семинары
Домашние задания
Контрольная работа
Будет проведена одна контрольная работа (ориентировочно) после 6-го занятия.
Экзамен
Оценка
Итог = min(10, Округление(0.25 * ДЗ + 0.25 * КР + 0.5 * Э)), где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, Э — оценка за экзамен. Округление арифметическое.
Книги
Основная литература
- [A] Акритас А.Г. Основы компьютерной алгебры с приложениями. 1994
- [АУ] Алфутова Н. Б., Устинов А. В. Алгебра и теория чисел. Сборник задач для математических школ. М.: МЦНМО, 2018
- [Б] Бухштаб А. А., Теория чисел
- [ВЭБ] Винберг Э. Б. Курс алгебры
- [ВИМ] Виноградов И. М., Основы теории чисел.
- [НК] Ноден П., Китте К. Алгебраическая алгоритмика
- [Х] Хинчин А. Я., Цепные дроби.
- [M] Menezes A., Oorschot P. van, Vanstone S. Handbook of Applied Cryptography
Дополнительная литература
- Василенко, О. Н. Теоретико-числовые методы в криптографии МЦНМО, 2003
- Герман, О. Н., Нестеренко, Ю. Теоретико-числовые методы в криптографии 2012
- Глухов М. М., Круглов И.А., Пичкур А.Б., Черёмушкин А.В. Введение в теоретико-числовые методы криптографии Лань, 2011
- Кнут, Д. Е. Искусство программирования для ЭВМ. Том 2: Получисленные алгоритмы "Вильямс" , М., Санкт-Петербург, Киев, 2000
- Коблиц Н. Курс теории чисел и криптографии. М.: ТВП, 2001.
- Ноден, П., Китте, К. Алгебраическая алгоритмика. Изд-во Мир, Москва, 1999
- Ященко, В. В. (Ed.) Введение в криптографию, МЦНМО, Москва, 1999
- Hoffstein, J.; Pipher, J., Silverman, J. H. An introduction to mathematical cryptography Springer, 2008,