Программа экзамена по курсу «Теоретико-числовые методы криптографии»

ТЕМА № 1. Сложность арифметических операций.

1.  Понятие алгоритма, сложности. Функции сложности алгоритмов и соотношения между ними.
2.   Понятие модели вычислений. Оценки функций сложности. Лемма о соотношении между двумя функциями, удовлетворяющим определенным условиям.
3.   Лемма о виде целочисленной функции.
4.   Теорема о сложности арифметических операций с целыми числами. Доказательство с применением итерационного метода Ньютона и алгоритма Карацубы-Офмана. Эффективность алгоритма Шенхаге-Штрассена.
5.   Делимость целых чисел. Алгоритм Евклида. Теорема Ламе о числе делений в алгоритме Евклида.
6.   Расширенный алгоритм Евклида. Теорема о существовании линейной комбинации, равной НОД двух чисел.
7.   Функция Эйлера. Операции в кольце вычетов. Метод Монтгомери для умножения целых чисел в кольце вычетов.
8.   Китайская теорема об остатках и ее следствие.
9.   Трудоемкость применения китайской теоремы об остатках.
10.Вычисления с многочленами. Алгоритм Руфини-Горнера и теорема о
его корректности. 
11. Дискретное преобразование Фурье и его применение для вычисления
произведения многочленов.

Тема № 2. Непрерывные (цепные) дроби.

12.Понятие непрерывной дроби. Теорема о фундаментальном
соответствии.
13.Подходящие дроби и их свойства. 
14.Представление действительных чисел непрерывными дробями. Лемма
о подходящих дробях. 
15.Теоремы  о  представлении рациональных  и  иррациональных чисел
непрерывными дробями.

Тема № 3 Квадратичные вычеты.

16.Понятие квадратичного вычета. Количество квадратичных вычетов.
17.Символ Лежандра и его свойства.
18. Лемма о сравнениях.
19.Квадратичный закон взаимности Гаусса.
20.Метод вычисления символа Лежандра.
21.Символ Якоби. Закон взаимности для символа Якоби. Вычисление
символа Лежандра с использованием символа Якоби. 22.Методы вычисления квадратичных вычетов.

Тема № 4. Простые числа.

23.Лемма об оценке функции Чебышева.
24. У прощенная теорема Чебышева и ее следствия.
25.Методы проверки простоты чисел. Критерий Вильсона.
26.Малая теорема Ферма и тест на простоту на основе малой теоремы
Ферма.
27.Псевдопростые числа и их свойства. Числа Кармайкла. 
28.Лемма Гаусса о цикличности мультипликативной группы примарного
кольца вычетов. Формулировка теоремы Гаусса. 
29.Теорема Кармайкла.
30.Тест Соловея-Штрассена и его критерий простоты. 
31.Тест Миллера-Рабина. Псевдопростые числа по основанию а. 
32.Критерий простоты и основанный на нем полиномиальный тест
распознавания простоты.
33.Теорема Люка. Эквивалентные формулировки Сэлфриджа. 
34.Теорема Пепина. 35.1-я теорема Поклингтона. 
36.2-я теорема Поклингтона. 
37.Теоремы Прота. 
38.Теорема Диемитко и ее лемма. 
39.Метод Маурера. Лемма № 1.
40.Метод Маурера. Лемма № 2 (Коувера-Куискуотера).
 41.Метод Маурера. Лемма о числе элементов, порядок которых делится на
заданное d. 
42.Теорема о вероятности успеха при доказательстве простоты и ее
следствие.
43.Метод Михалеску. 
44.Понятие об п+1 - методах доказательства простоты. Формулировки
основных утверждений. Числа Мерсенна.

Тема № 5. Факторизация.

45.Метод пробных делений и его трудоемкость.
46.Ро-метод Полларда и его модификация. Теорема об эффективности.
Примеры.
47.Метод Ферма и его обоснование. Примеры. 
48.(р-1)-метод Поларда, Примеры. 
49.Алгоритм факторных баз. Примеры.
50.Факторизация с помощью цепных дробей и его обоснование. Примеры. 
51 .Метод квадратичного решета. 
52.Основная идея метода решета числового поля.
 53.Последовательность Крылова над произвольным полем. Лемма о линейной зависимости. 
54.Ортогонализация последовательности Крылова. Леммы о самоортогональных векторах.
55.Выражение решения системы линейных уравнений через
ортогонализованную последовательность Крылова. 
56.Модифицированный процесс ортогонализации. Алгоритм Ланцоша. 
57.Нахождение минимального многочлена последовательности с
помощью алгоритма Берлекемпа-Месси. 
58.Алгоритм Видемана решения систем линейных уравнений.

Тема № 6. Эллиптические кривые.

59.Понятие эллиптической кривой над полем. Операции над точками
эллиптической кривой. Порядки точек. Примеры. 
60.Порядок точки эллиптической кривой. Примеры. Кратные точки на
эллиптических кривых. Сложность вычисления кратных точек. 
61.Эллиптические кривые над расширением конечным полем. Теорема
Хассе (без док.) Тип эллиптической кривой.
62.Эллиптические кривые над расширением конечного поля. Дзета-функция эллиптической кривой. Теорема Вейля (без док.). Примеры. 63.Применение эллиптических кривых для проверки простоты чисел.
Условие простоты целого числа в терминах эллиптических кривых.
Алгоритм доказательства простоты. 
64.Метод Ленстры факторизации целых чисел с помощью эллиптических кривых и его обоснование, (без док.).

Тема № 7. Криптография с открытым ключом.

65.Суть криптографии с открытым ключом. Основные алгоритмы:
хеширование, аутентификация. 
66.Криптосистема RSA: принципы построения, основные условия на
выбор параметров.
67.Криптосистемы, основанные на задаче дискретного логарифмирования. 
68.Криптосистемы на эллиптических кривых. Примеры.