|
Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.mccme.ru/dubna/2006/courses/amerik.html
Дата изменения: Fri Jul 14 17:38:08 2006 Дата индексирования: Sat Dec 22 15:30:56 2007 Кодировка: koi8-r Поисковые слова: каллисто |
Е.Ю.Америк планирует провести 2 занятия.
Вначале будет рассказано о некоторых криптосистемах с открытым ключом — в частности, о знаменитой RSA. В основе таких криптосистем лежат так называемые «односторонние функции». Это такие функции f из множества сообщений в множество криптограмм (зависящие от параметра, «ключа»), что любое значение f можно вычислить достаточно быстро, в то время как вычисление f –1 настолько трудно, что оно оказывается неосуществимым на практике за разумное время.
Один из источников «односторонних функций» — арифметика в кольце Z/nZ. При этом естественно возникают некоторые «алгоритмические» вопросы арифметики: как построить «большое» простое число? Как проверить «большое» число на простоту? Как разложить «большое» составное число на множители? Я постараюсь рассказать о некоторых алгоритмах, которые для этого используются.
Наконец, я надеюсь рассказать — очень кратко и, как правило, без доказательств — об эллиптических кривых и их применении в криптографии и алгоритмических проблемах.
Желательно некоторое знакомство с начальными понятиями алгебры (группа, кольцо, поле, теорема Лагранжа) и арифметики (алгоритм Евклида, кольцо Z/nZ, китайская теорема об остатках).
