Изменения
Нет описания правки
# В определении $ZPP$ нет требования, чтобы на любой вероятностной ленте программа завершалась. Докажите, что если добавить это ограничение, определение класса $ZPP$ не поменяется.
# При симуляции $random(n)$ с помощью бросков честной монеты (или абстракции вероятностной ленты) математическое ожидание времени работы $random(n)$ равно $O(\log n)$, но нет ограничения сверху на число бросков. Кажется, что это может испортить определение классов $RP$ или $BPP$, потому что в них время работы программы должно быть ограничено сверху. Докажите, что это не так и можно разрешить конструкции $random(n)$ в вероятностных программах из определения $RP$ или $BPP$, даже если на самом деле в модели вычислений есть доступ к источнику случайности только с распределением честной монеты.
# Пусть $n = pq$, предложите полиномиальный алгоритм, который по заданным $n$ и $\varphi(n)$ находит $p$ и $q$.
# Факторизация через взлом RSA. Пусть $n = pq$, $ed = 1 \pmod \varphi(n)$, полиномиальный алгоритм по заданным $n$ и $e$ находит $d$. Докажите, что существует полиномиальный алгоритм, который по заданному $n$ находит $p$ и $q$.
# Плохое $e$. Почему в алгоритме RSA нельзя использовать $e=2$?
# Плохое $e$. Петя отправляет сообщение $x$ Алисе, Бобу и Чарли. Они все трое используют RSA с открытым ключом $e=3$ и разными $n_1$, $n_2$ и $n_3$. Помогите злоумышленнику, который перехватил все три зашифрованных сообщения, восстановить $x$. Сможет ли он восстановить $d_i$?
# Переиспользование $n$. Петя отправляет сообщение $x$ Алисе и Бобу. Оба используют RSA с открытыми ключами $e_1$ и $e_2$ и одинаковым $n$. Помогите злоумышленнику, который перехватил оба зашифрованных сообщения, восстановить $x$. Сможет ли он восстановить $d_i$?
# Бросок монеты по телефону. Используя алгоритм слепой цифровой подписи предложите алгоритм, который позволяет Алисе и Бобу подбросить честную монету по телефону. Честная монета у каждого из них есть, в результате общения каждый из них должен иметь одно и то же значение $x$ и его априорное распределение должно быть как у честной монеты.
