• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Теоретико-числовые методы в криптографии

2019/2020
Учебный год
RUS
Обучение ведется на русском языке
3
Кредиты
Статус:
Курс обязательный
Когда читается:
4-й курс, 3, 4 модуль

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

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

Аннотация

Данная дисциплина относится к базовой части Профессионального цикла (Major), проводится на 4 курсе обучения и является обязательной. Для освоения учебной дисциплины студенты должны владеть базовыми знаниями и компетенциями, полученными при изучении следующих дисциплин: основными понятиями алгебры, теории конечных групп, колец и полей, основными понятиями элементарной теории чисел. Результаты освоения дисциплины используются в дальнейшем при прохождении производственной и преддипломной практик, при выполнении выпускной квалификационной работы, а также при изучении таких дисциплин, как криптографические методы защиты информации, криптографические протоколы, методы алгебраической геометрии в криптографии.
Цель освоения дисциплины

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

  • Формирование у студентов навыков, необходимых для разработки математических моделей защищаемых процессов и средств защиты информации и систем, обеспечивающих информационную безопасность
  • Формирование у студентов навыков, необходимых для обоснования и выбора рационального решения по уровню обеспечения защищенности компьютерной системы с учетом заданных требований
  • Формирование у студентов навыков, необходимых для подготовки научно-технических отчетов, обзоров, публикаций по результатам выполненных исследований
  • Формирование у студентов навыков, необходимых для выполнения экспериментально-исследовательских работ при проведении сертификации средств защиты и анализ результатов
  • Формирование у студентов навыков, необходимых для проведения аттестации технических средств, программ, алгоритмов на предмет соответствия требованиям защиты информации по соответствующим классам безопасности или профилям защиты
Планируемые результаты обучения

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

  • Знать алгоритмы построения простых чисел
  • Уметь строить простые числа заданного размера
  • Владеть навыками нахождения корней многочленов над конечным простым полем
  • Знать алгоритмы проверки больших целых чисел на простоту
  • Уметь решать задачу разложения больших целых чисел на множители
  • Владеть навыками построения простых чисел заданного размера
  • Знать алгоритмы факторизации больших целых чисел
  • Уметь решать задачу дискретного логарифмирования
  • Владеть навыками разложения чисел на множители и вычисления дискретных логарифмов в мультипликативной группе конечного простого поля
  • Знать методы дискретного логарифмирования в циклических группах
  • Знать методы нахождения корней многочленов над конечными полями
  • Уметь доказывать простоту больших целых чисел
  • Владеть навыками вычисления символа Лежандра
Содержание учебной дисциплины

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

  • Сведения из элементарной теории чисел: наибольший общий делитель, алгоритм Эвклида вычисления НОД и его модификации, бесконечность множества простых чисел, основная теорема арифметики
  • Сравнения первой степени. Китайская теорема об остатках. Функция Эйлера. Показатели и первообразные корни. Теоремы о существовании и количестве первообразных корней. Алгоритмы построения первообразных корней.
  • Теория и свойства многочленов от одной переменной, лемма Безу, основная теорема арифметики для многочленов. Дифференцирование многочленов. Решение полиномиальных сравнений по составному модулю -- сведение решений в конечных кольцах к случаю конечного простого поля. Метод подъема решения
  • Сравнения старших степеней по простому модулю. Квадратичные вычеты. Символы Лежандра и Якоби. Алгоритмы вычисления символа Лежандра
  • Вычисление корней второй степени. Алгоритм Тонелли-Шенкса вычисления квадратных корней по простому модулю. Алгоритм, основанный на квадратичных расширениях конечного простого поля
  • Методы вычисления корней третьей степени. Элементы теории двучленных сравнений. Вероятностный алгоритм вычисления корней многочленов старших степеней
  • Простые числа. Бесконечность множества простых чисел. Методы построения таблиц простых чисел
  • Вероятностные тесты проверки на простоту: числа Кармайкла, тест Соловея-Штрассена и тест Милера-Рабина
  • Алгоритмы доказательства простоты чисел с использованием разложения n-1 на простые множители (теоремы Лемера и Поклингтона)
  • Алгоритмы доказательства простоты чисел с использованием разложения n+1 на простые множители (теорема Морисона)
  • Рассмотрение обобщения указанных алгоритмов. Алгоритмы построения строго простых чисел
  • Полиномиальный алгоритм доказательства простоты
  • Цепные дроби. Понятие подходящей дроби. Квадратичные иррациональности и их разложения в цепные дроби. Наилучшие приближения действительных чисел
  • Экспоненциальные методы факторизации целых чисел. Метод Ферма, методы Полларда-Флойда и Брента. p-1 метод Полларада, p+1 метод Вильямса. Методы оптимизации рассмотренных алгоритмов
  • Решето Крайчика. Метод непрерывных дробей (Лемера), метод Моррисона-Бриллхарда, метод квадратичного решета и его дальнейшие модификации
  • Алгоритмы вычисления индексов (решения задачи дискретного логарифмирования): метод согласования, методы Нечаева и Поллига-Хеллмана. Методы, основанные на поиске длин циклов в последовательностях: методы Полларда, Госпера, а также параллельный метод Винера
  • Индекс методы решения задачи дискретного логарифмирования. Решение систем линейных уравнений в кольцах вычетов. Индекс-метод Адлемана и его модификации
Элементы контроля

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

  • неблокирующий Контрольная работа 1
  • неблокирующий Контрольная работа 2
  • неблокирующий Экзамен
Промежуточная аттестация

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

  • Промежуточная аттестация (4 модуль)
    0.25 * Контрольная работа 1 + 0.25 * Контрольная работа 2 + 0.5 * Экзамен
Список литературы

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

Рекомендуемая основная литература

  • Angelo Koudou, & Christophe Ley. (2014). Efficiency combined with simplicity: new testing procedures for Generalized Inverse Gaussian models. TEST: An Official Journal of the Spanish Society of Statistics and Operations Research, 4, 708. https://doi.org/10.1007/s11749-014-0378-2
  • Сгибнев А.И. - Делимость и простые числа - Московский центр непрерывного математического образования - 2015 - 112с. - ISBN: 978-5-4439-0340-8 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/71820

Рекомендуемая дополнительная литература

  • Bruno Aiazzi, Stefano Baronti, Leonardo Santurri, & Massimo Selva. (2019). An Investigation on the Prime and Twin Prime Number Functions by Periodical Binary Sequences and Symmetrical Runs in a Modified Sieve Procedure. https://doi.org/10.3390/sym11060775