|
|
| Строка 1: |
Строка 1: |
| − | {| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
| |
| − | |+
| |
| − | |-align="center"
| |
| − | |'''НЕТ ВОЙНЕ'''
| |
| − | |-style="font-size: 16px;"
| |
| − | |
| |
| − | 24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
| |
| − |
| |
| − | Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
| |
| − |
| |
| − | Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
| |
| − |
| |
| − | Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
| |
| − |
| |
| − | ''Антивоенный комитет России''
| |
| − | |-style="font-size: 16px;"
| |
| − | |Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
| |
| − | |-style="font-size: 16px;"
| |
| − | |[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
| |
| − | |}
| |
| − |
| |
| | ==Формулировка== | | ==Формулировка== |
| | | | |
Текущая версия на 19:14, 4 сентября 2022
Формулировка
Имеется схема шифрования [math](E, D)[/math] с набором из [math]k = 2^{n}[/math] ключей. Будем обозначать шифрующую функцию с ключом [math]i[/math] как [math]E_{i}[/math], а функцию для расшифрования с тем же ключом как [math]D_{i}[/math]. Обе функции биективны. То есть при любом [math]i[/math] выполняется следующее: [math]E_{i}(x) = c \Leftrightarrow D_{i}(c) = x[/math]. На схему подаются слова длины [math]m[/math], при этом [math]m \gt n[/math].
Тогда, если P [math]=[/math] NP, то существует функция [math] A: \{0,1\}^{m} \to \{0,1\}[/math], вычислимая за полиномиальное время от входа, такая, что для нее в свою очередь существуют слова [math]x_{0}[/math] и [math]x_{1}[/math] такие, что вероятность [math]P(A(E_{i}(x_{b}))=b) \ge 0.75[/math] по всем [math]b \in \{0,1\}[/math] и всем [math]i \in \{0,1\}^{n}[/math].
Если P [math]=[/math] NP, то получается, что для любой схемы шифрования с количеством ключей меньше, чем длина шифруемых слов, найдется пара таких слов, которые можно различить с высокой вероятностью. С другой стороны, как будет видно из доказательства, эта пара слов неконструктивна.
Доказательство
Рассмотрим язык [math]S = \{ y | \exists i \in \{0,1\}^{n}: y = E_{i}(0^{m})\}[/math]. Заметим, что этот язык лежит в NP. Сертификатом для слова [math]y[/math] является номер [math]i[/math] шифрующей функции [math]E_{i}[/math] такой, что [math]y = E_{i}(0^{m})[/math]. Так как NP [math]=[/math] P, то [math]S[/math] лежит в классе P. А тогда существует функция [math]A(y) \in P[/math], равная нулю, если [math]y \in S[/math], и единице в противном случае.
Оценим вероятность [math]P(A(E_{i}(x_{b})) = b)[/math] при [math]x_{0} = 0^{m}[/math] и некотором [math]x_{1}[/math]. Заметим, что так как [math]b[/math] равновероятно может быть и нулем, и единицей, то:
[math]P(A(E_{i}(x_{b})) = b) = 0.5 \cdot P(A(E_{i}(x_{0})) = 0) + 0.5 \cdot P(A(E_{i}(x_{1})) = 1)[/math].
[math]E_{i}(x_{0})[/math] лежит в [math]S[/math] при любом [math]i[/math] по определению [math]S[/math] и выбору [math]x_{0}[/math]. Таким образом [math]P(A(E_{i}(x_{0})) = 0) = 1[/math].
Докажем теперь, что [math]\exists x_{1}[/math] такой, что [math]P(A(E_{i}(x_{1})) = 1) \ge 0.5[/math]. Так как каждая шифрующая функция [math]E_{i}[/math] биективна, а [math]|S| \le 2^{n}[/math], то [math]\sum \limits_{x} A(E_{i}(x)) \ge 2^{m} - 2^{n}[/math] для любого [math]i[/math]. Тогда [math]\sum \limits_{i} \sum \limits_{x} A(E_{i}(x)) = \sum \limits_{x} \sum \limits_{i} A(E_{i}(x)) \ge 2^{n} (2^{m} - 2^{n})[/math]. Из этого неравенства следует, что не может быть для любого [math]x[/math]: [math]\sum \limits_{i} A(E_{i}(x)) \lt 2^{n} (1 - 2^{n-m})[/math]. Следовательно, [math]\exists x_{1}[/math] такой, что [math]\sum \limits_{i} A(E_{i}(x_{1})) \ge 2^{n} (1 - 2^{n-m}) \ge 2^{n-1}[/math], а вероятность по всем [math]i \in \{0,1\}^{n}[/math] [math]P(A(E_{i}(x_{1})) = 1) \ge 0.5[/math].
Таким образом [math]P(A(E_{i}(x_{b})) = b) \ge 0.5 \cdot 1 + 0.5 \cdot 0.5 = 0.75[/math].
