ПРОГРАММА КУРСА
Криптографические конструкции
(годовой, для всех желающих, лектор чл.-корр. РАН Ю.В. Нестеренко)
- Алгоритмы и сложность.
- Алгоритм Евклида, теорема Ламе о сложности этого алгоритма.
- Быстрое умножение целых чисел.
- Быстрый алгоритм возведения в степень.
- Вероятностные алгоритмы. Быстрый вероятностный алгоритм вычисления квадратичного невычета.
- Псевдослучайные последовательности чисел.
- Быстрый вероятностный алгоритм решения полиномиальных сравнений по большому простому модулю.
- Быстрый алгоритм построения первообразных корней по простому модулю.
- Алгоритмы отсеивания составных чисел. Полиномиальный алгоритм проверки чисел на простоту (без доказательства).
- Построение больших простых чисел.
- Задача факторизации целых чисел.
- Задача дискретного логарифмирования.
- Информационные технологии.
- Шифрование и расшифрование (немного истории).
- Ключевой обмен.
- Алгоритм RSAшифрования и расшифрования информации.
- Электронная цифровая подпись.
- Эллиптические кривые над полем вычетов по простому модулю p.
- Цифровая подпись с помощью эллиптических кривых.
- Простейшие булевы функции.
- Хеш-функции.
- Схемы обязательств.
- Разделение секрета.
- Электронное голосование.
- Технологии блокчейн (blockchain).
- Криптовалюты.
Творческая работа (для двух небольших групп школьников).
- Построить алгоритм и соответствующую компьютерную программу, производящие простые числа на заданном интервале. Например, от 3^500 до 2^1000 = 4^500.
- Построить систему удалённого электронного голосования для СУНЦ.