Е.Ю.Америк планирует провести 2 занятия.
Вначале будет рассказано о некоторых криптосистемах с открытым ключом — в частности, о знаменитой RSA. В основе таких криптосистем лежат так называемые «односторонние функции». Это такие функции f из множества сообщений в множество криптограмм (зависящие от параметра, «ключа»), что любое значение f можно вычислить достаточно быстро, в то время как вычисление f –1 настолько трудно, что оно оказывается неосуществимым на практике за разумное время.
Один из источников «односторонних функций» — арифметика в кольце Z/nZ. При этом естественно возникают некоторые «алгоритмические» вопросы арифметики: как построить «большое» простое число? Как проверить «большое» число на простоту? Как разложить «большое» составное число на множители? Я постараюсь рассказать о некоторых алгоритмах, которые для этого используются.
Наконец, я надеюсь рассказать — очень кратко и, как правило, без доказательств — об эллиптических кривых и их применении в криптографии и алгоритмических проблемах.
Желательно некоторое знакомство с начальными понятиями алгебры (группа, кольцо, поле, теорема Лагранжа) и арифметики (алгоритм Евклида, кольцо Z/nZ, китайская теорема об остатках).
