Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Теоретико-числовые алгоритмы и криптография
Санкт-Петербург / осень 2019, посмотреть все семестры

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

Курс будет покрывать следующие темы:

  1. Предварительные сведения из теории чисел (полная и приведенная системы вычетов, теорема Вильсона, малая теорема Ферма, функция и теорема Эйлера, китайская теорема об остатках, алгоритм Гарнера, квадратичные вычеты, символы Лежандра и Якоби, показатель числа по модулю, первообразный корень).
  2. Простейшие криптосистемы и их взлом (Сцитала, шифр Цезаря, квадрат Виженера, шифр Вернама, Энигма)
  3. Зачем все это нужно (схема Диффи-Хеллмана, шифры Шамира и Эль-Гамаля, RSA, функция Рабина).
  4. Проверка чисел на простоту (тест на основе МТФ, тесты Соловея-Штрассена, Рабина-Миллера и Миллера, числа Кармайкла).
  5. Доказательство простоты и построение больших простых чисел (n-1 и n+1 методы, метод Маурера, алгоритм Агравала-Кайала-Саксены)
  6. Дискретное логарифмирование (шаг младенца-шаг великана, алгоритм Полига-Хеллмана, алгоритм исчисления порядка).
  7. Электронные протоколы для популярных задач (разделение секрета, ставки, жребий, раздача карт, аутентификация, электронная подпись и т.д.).
  8. Факторизация целых чисел (метод Ферма, метод Шермана-Лемана, ро-метод Полларда, алгоритм Полларда-Штрассена, метод Диксона).