Бакалавриат
2024/2025
Теория чисел
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 3 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
3
Программа дисциплины
Аннотация
Этот курс основ теории чисел, который содержит такие базовые разделы как алгоритм Евклида, цепные дроби, арифметические функции, теория сравнений, квадратичные вычеты, первообразные корни. Параллельно будет происходить знакомство с задачами математической криптографии и простейшими криптографическими протоколами.
Цель освоения дисциплины
- Знать свойства квадратичных вычетов.
- Знать свойства первообразных корней и дискретных логарифмов.
- Уметь доказывать корректность работы базовых криптографичеких протоколов и обосновывать их стойкость.
Планируемые результаты обучения
- Знать базовые арифметические функции и их свойства
- Знать базовые алгоритмы целочисленной арифметики. Уметь оценивать их сложность.
- Знать основные результаты теории сравнений (малая теорема Ферма, теорема Эйлера, китайская теорема об остатках).
- Знать свойства квадратичных вычетов.
- Знать свойства первообразных корней и дискретных логарифмов.
- Уметь доказывать корректность работы базовых криптографичеких протоколов и обосновывать их стойкость.
Содержание учебной дисциплины
- Алгоритмы и их сложность. Классические алгоритмы целочисленной арифметики. Алгоритм Евклида. Конечные цепные дроби.
- Обобщённая лемма Евклида. Основная теорема арифметики. Линейные диофантовы уравнения от двух неизвестных.
- Сравнения по модулю, классы вычетов, критерий обратимости вычета по умножению, теорема Вильсона, теорема о полной и приведённой системах вычетов, теорема Эйлера, малая теорема Ферма.
- Криптографическая система RSA, понятие решения полиномиального сравнения, китайская теорема об остатках. Количество решений полиномиального сравнения по простому модулю
- Решение полиномиальных сравнений. Лемма Гензеля.
- Квадратичные вычеты. Критерий Эйлера квадратичности вычета, символ Лежандра и его элементарные свойства.
- Лемма Гаусса о символе Лежандра, вывод формулы для символа Лежандра от двойки, доказательство квадратичного закона взаимности Гаусса.
- Символ Якоби и его свойства, тест Соловея-Штрассена.
- Доказательство теоремы о тесте Соловея-Штрассена, определение показателя вычета по модулю, делимость значения функции Эйлера на показатель, теорема о количестве первообразных корней в приведённой системе вычетов.
- Доказательство существования первообразных корней по простому модулю, протокол Диффи-Хеллмана построения общего ключа шифрования, криптографическая система Эль-Гамаля.
Элементы контроля
- Домашнее задание 1
- Домашнее задание 2
- Контрольные работыОдна контрольная работа проводятся (ориентировочно) после 6-го занятия.
- ЭкзаменЭкзамен письменный. Билет включает в себя 2-3 теоретических вопроса из программы экзамена и 6-8 задач. Во время подготовки использовать любые материалы запрещается.
Промежуточная аттестация
- 2024/2025 3rd moduleНакопленная Оценка, НО, вычисляется без округления по следующей формуле: НО = 0.4 * ДЗ + 0.2 * Кр + 0.4 * КЛ. Итоговая Оценка за Курс, ИО, вычисляется по следующей формуле: ИО = Округление(7/10*НО + 3/10*ЭК), где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, ЭК — оценка за экзамен, КЛ ¬– оценка за коллоквиум. Если НО не меньше 8 (без округления), то студент может не сдавать экзамен. В этом случае ИО = Округление(НО). Округление арифметическое.
Список литературы
Рекомендуемая основная литература
- Виноградов, И. М. Основы теории чисел / И. М. Виноградов. — Москва : Издательство Юрайт, 2024. — 123 с. — (Антология мысли). — ISBN 978-5-534-12085-1. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/540613 (дата обращения: 27.08.2024).
Рекомендуемая дополнительная литература
- Ларин, С. В. Алгебра и теория чисел. Группы, кольца и поля : учебное пособие для вузов / С. В. Ларин. — 2-е изд., испр. и доп. — Москва : Издательство Юрайт, 2020. — 160 с. — (Высшее образование). — ISBN 978-5-534-05567-2. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/454465 (дата обращения: 27.08.2024).