Кто читает:: Департамент больших данных и информационного поиска

Статус:: Курс по выбору

Когда читается:: 1-й курс, 3 модуль

Преподаватели

Герман Олег Николаевич

Радомский Артем Олегович

Устинов Алексей Владимирович

Фроленков Дмитрий Андреевич

Юделевич Виталий Викторович

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

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

Цель освоения дисциплины

Знать свойства квадратичных вычетов.
Знать свойства первообразных корней и дискретных логарифмов.
Уметь доказывать корректность работы базовых криптографичеких протоколов и обосновывать их стойкость.

Планируемые результаты обучения

Знать базовые арифметические функции и их свойства
Знать базовые алгоритмы целочисленной арифметики. Уметь оценивать их сложность.
Знать основные результаты теории сравнений (малая теорема Ферма, теорема Эйлера, китайская теорема об остатках).
Знать свойства квадратичных вычетов.
Знать свойства первообразных корней и дискретных логарифмов.
Уметь доказывать корректность работы базовых криптографичеких протоколов и обосновывать их стойкость.

Содержание учебной дисциплины

Алгоритмы и их сложность. Классические алгоритмы целочисленной арифметики. Алгоритм Евклида. Конечные цепные дроби.
Обобщённая лемма Евклида. Основная теорема арифметики. Линейные диофантовы уравнения от двух неизвестных.
Сравнения по модулю, классы вычетов, критерий обратимости вычета по умножению, теорема Вильсона, теорема о полной и приведённой системах вычетов, теорема Эйлера, малая теорема Ферма.
Криптографическая система RSA, понятие решения полиномиального сравнения, китайская теорема об остатках. Количество решений полиномиального сравнения по простому модулю
Решение полиномиальных сравнений. Лемма Гензеля.
Квадратичные вычеты. Критерий Эйлера квадратичности вычета, символ Лежандра и его элементарные свойства.
Лемма Гаусса о символе Лежандра, вывод формулы для символа Лежандра от двойки, доказательство квадратичного закона взаимности Гаусса.
Символ Якоби и его свойства, тест Соловея-Штрассена.
Доказательство теоремы о тесте Соловея-Штрассена, определение показателя вычета по модулю, делимость значения функции Эйлера на показатель, теорема о количестве первообразных корней в приведённой системе вычетов.
Доказательство существования первообразных корней по простому модулю, протокол Диффи-Хеллмана построения общего ключа шифрования, криптографическая система Эль-Гамаля.

Элементы контроля

Домашнее задание 1
Домашнее задание 2
Контрольные работы
Одна контрольная работа проводятся (ориентировочно) после 6-го занятия.
Экзамен
Экзамен письменный. Билет включает в себя 2-3 теоретических вопроса из программы экзамена и 6-8 задач. Во время подготовки использовать любые материалы запрещается.

Промежуточная аттестация

2024/2025 3rd module
Накопленная Оценка, НО, вычисляется без округления по следующей формуле: НО = 0.4 * ДЗ + 0.2 * Кр + 0.4 * КЛ. Итоговая Оценка за Курс, ИО, вычисляется по следующей формуле: ИО = Округление(7/10*НО + 3/10*ЭК), где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, ЭК — оценка за экзамен, КЛ ¬– оценка за коллоквиум. Если НО не меньше 8 (без округления), то студент может не сдавать экзамен. В этом случае ИО = Округление(НО). Округление арифметическое.

Список литературы

Авторы

Устинов Алексей Владимирович
Рословцева Кристина Олеговна

Бакалаврская программа «Прикладная математика и информатика»

Менеджер

По вопросам поступления консультирует

Адрес

Теория чисел

Преподаватели

Программа дисциплины