Спецкурс об односторонних функциях на мехмате МГУ

[Alexander V. Smal]

Добрый вечер!

Пересылаю сообщение от Николая Константиновича Верещагина про спецкурс
на мехмате МГУ. По времени этот спецкурс пересекается с курсом по
теории вычислительной сложности, но при этом предполагает знание этого
начал теории сложности. Поэтому я бы рекомендовал его тем, кто уже
слушал курс по теории сложности.

===
14 сентября начнется полугодовой спецкурс Н.К. Верещагина
"Односторонние функции и их применения", который будет читаться онлайн
по вторникам с 18:30 до 20:05.

Функция f, отображающая слова в слова, называется односторонней, если
по x можно найти f(x) за полиномиальное от длины x время, однако в
обратную сторону
по f(x) найти x или какой-то другой прообраз f(x) за
полиномиальное время можно только на ничтожной доле входов. В
спецкурсе будут доказаны основные факты об односторонних функциях.
Будет рассказано, как односторонние функции применяются в криптографии
для построения доказуемо надежных генераторов псевдослучайных чисел,
схем шифрования с открытым и закрытым ключом, протоколов привязки,
протоколов бросания монетки по телефону и протоколов идентификации.

Необходимы предварительные знания: начала сложности вычислений (машины
Тьюринга, схемы из функциональных элементов, взаимотношения между
ними, вероятностные алгоритмы, классы P, BPP, NP).

Ссылка на сайт курса: http://logic.math.msu.ru/staff/ver/kursy/owf/

На спецкурс об односторонних функциях можно записаться через сервис
http://scs.math.msu.ru/enroll
===

Саша

--
Alexander V. Smal
St. Petersburg Department of Steklov Mathematical Institute
27 Fontanka, St. Petersburg, 191023, Russia

[Alexander V. Smal]

Ссылка в предыдущем письме только для студентов МГУ.
Инструкцию для внешних студентов пришлю позже.

Саша

[Alexander V. Smal]

Ссылка для подключения опубликована на странице курса:
http://logic.math.msu.ru/staff/ver/kursy/owf/

Саша