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

Теоретико-числовые методы в криптографии 9 семестр Лекция 1 Литература. 1. Черемушкин А.В. Лекции по арифметическим алгоритмам в криптографии. М.: МЦНМО, 2002. 2. Коблиц Н. Курс теории чисел и криптографии. М.: Научное изд-во ТВП, 2001. RSA Примерный список вопросов на экзамен 1. Понятие сложности алгоритма. Свойства функций оценки сложности. Леммы о сложности рекурсивных алгоритмов. 2. Сложность арифметических операций в кольце целых чисел. Алгоритм Карацубы умножения целых чисел. Алгоритм возведение в степень. 3. Сложность основного и расширенного алгоритма Евклида. 4. Бинарный расширенный алгоритм нахождения НОД, его сложность. 5. Сложность вычислений в кольцах вычетов. Алгоритм Монтгомери и его сложность. 6. Алгоритмы реализации китайской теоремы об остатках, их сложность. 7. Решение уравнения f(x)=0 в кольце вычетов по примарному модулю. 8. Решение уравнения f(x)=0 в кольце вычетов по простому модулю (вероятностный алгоритм с оценкой вероятности «успеха»). 9. Дискретное преобразование Фурье. Алгоритм БПФ, его сложность. 10. Квадратичные вычеты: определение и простейшие свойства. Символ Лежандра: определение и свойства (квадратичный закон взаимности Гаусса без доказательства), алгоритм вычисления. 11. Символ Лежандра. Определение и формулировки свойств. Доказательство квадратичного закона взаимности. 12. Символ Якоби. Определение и свойства. Алгоритм вычисления и его сложность. 13. Алгоритмы решения сравнений вида x2≡a по простому модулю вида 4k+3 или 8k+5 и их сложность. 14. Алгоритм решения сравнений вида x2≡a по простому модулю вида 4k+1 и его сложность. 15. Цепные дроби: определение, теорема о единственности представления рационального числа цепной дробью. Определение и простейшие свойства подходящих дробей. Алгоритм представления рационального числа цепной дробью и его сложность. 16. Определение цепной дроби. Подходящие дроби: определение и свойства. Теорема о единственности представления иррациональных чисел цепной дробью. Подходящие дроби как наилучшие приближения действительных чисел. 17. Периодические цепные дроби. Теорема Лагранжа. Алгоритм представления квадратичной иррациональности цепной дробью (без доказательства). 18. Цикличность мультипликативной группы кольца вычетов по нечетному примарному модулю. 19. Нецикличность мультипликативной группы кольца вычетов по четному примарному модулю, отличному от 2 и 4. 20. Критерий цикличности мультипликативной группы кольца вычетов. 21. Теорема Чебышева (формулировка). Доказательство оценки величины n-го простого числа. 22. Тест простоты на основе малой теоремы Ферма. Свойства псевдопростых по некоторому основанию чисел. 23. Числа Кармайкла. Определение и свойства. 24. Тест простоты Соловея-Штрассена. Оценка вероятности успеха. Эйлеровы псевдопростые числа: определение и свойства. 25. Тест простоты Миллера-Рабина. Сильно псевдопростые числа: определение и свойства, оценка вероятности «успеха» (оценка – без доказательства). 26. Критерий простоты Люка. Критерий простоты чисел Ферма. 27. Теорема Поклингтона. Достаточное условие простоты. 28. Метод Маурера генерации простых чисел. 29. r-метод факторизации Полларда. Оценка сложности. 30. Детерминированный алгоритм факторизации Полларда-Штрассена. Оценка сложности (идея доказательства). 31. Алгоритмы факторизации Диксона и Бриллхарта-Моррисона. Выбор факторной базы. Оценка сложности (идея доказательства). 32. RSA. Зависимость стойкости от выбора параметров. 33. RSA. Алгоритм генерации сильно простых чисел. 34. Дискретное логарифмирование Алгоритм В.И.Нечаева. Примеры криптосистем, основанных на вычислительной сложности задачи дискретного логарифмирования. 35. Общее уравнение эллиптической кривой. Изоморфные кривые. Уравнения кривой над полями различных характеристик. Формула для числа точек эллиптической кривой над Z/p при простом p>3. 36. Группа точек эллиптической кривой. Алгоритмы и их сложность Леммы оценки функции сложности рекурсивных алгоритмов Лекция 2 Сложность арифметических операций с целыми числами и в кольцах вычетов Лекция 3 Использование модульной арифметики. Сложность арифметических операций с матрицами Лекция 4 Вычисления в кольце многочленов Лекция 5 Преобразование Фурье. Алгоритм БПФ Лекция 6 Квадратичные вычеты Лекция 7 Символ Якоби 2 O(log n) Лекция 8 Лекция 8 Лекция 9 Цепные дроби Лекция 10 Цепные дроби Лекция 11 Критерий цикличности мультипликативной группы кольца вычетов. Теорема Чебышева о распределении простых чисел