City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Number-theoretic algorithms and cryptography


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

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

Course Offerings

Semester Branch
autumn 2019 Saint Petersburg