NP-полные задачи и криптография

[Munin]

Deggial: Обсуждение выделено из темы Чем вообще занимаются современные математики?
Тег оффтопа убран

g______d в сообщении #716119 писал(а):

(речь о P=NP) Прямых практических приложений у этой задачи не будет.

Здесь, видимо, оговорка. В одной криптографии целый мешок практических приложений будет.

[g______d]

Munin в сообщении #716164 писал(а):

g______d в сообщении #716119 писал(а):

(речь о P=NP) Прямых практических приложений у этой задачи не будет.

Здесь, видимо, оговорка. В одной криптографии целый мешок практических приложений будет.

Я имел в виду именно "прямых практических". Если внезапно окажется, что задача коммивояжера решается за $O(n^{10^{10^{10}}})$, то что, все сразу побегут взламывать SHA-256? Или какие там есть алгоритмы шифрования? Разумеется, это будет большим вкладом в теорию сложности, и приложения будут, но не прямые и не сразу.

[Munin]

В общем, да. Но нет гарантии, что не окажется, что задача коммивояжёра решается за $O(n^2\log n).$ (Если не доказано такой конкретной теоремы, о чём я точно не в курсе.) Мы, в общем, надеемся, что задача коммивояжёра сложна, и эта надежда основана именно на $P\stackrel{?}{=}NP,$ а не на конкретном виде полинома. Кстати, SHA-256, насколько я знаю, не на задаче коммивояжёра основана: если задачу коммивояжёра и "взломают", на другие $NP$-задачи распространить это может потребоваться ещё лет 50.

[Xaositect]

Munin в сообщении #716352 писал(а):

Кстати, SHA-256, насколько я знаю, не на задаче коммивояжёра основана: если задачу коммивояжёра и "взломают", на другие $NP$-задачи распространить это может потребоваться ещё лет 50.

Нет, там все сводимости от одной задачи к другой достаточно простые, и по времени как правило не больше $n^3$

[Munin]

Xaositect в сообщении #716356 писал(а):

Нет, там все сводимости от одной задачи к другой достаточно простые

А. Не знал. Спасибо. Да, этот пункт снимается.

[AV_77]

И как давно SHA-2 относится к NP-полным задачам?

[g______d]

Да, я, наверное, в этом не прав. Я вообще не нашел ни одного алгоритма шифрования, взлом которого NP-сложен.

Впрочем, это только подтверждает мое высказывание.

[AV_77]

g______d в сообщении #716423 писал(а):

Я вообще не нашел ни одного алгоритма шифрования, взлом которого NP-сложен.

Хм... это странно. RSA чем не подходит? Или алгоритмы на основе дискретного логарифмирования?

[Xaositect]

g______d в сообщении #716423 писал(а):

алгоритма шифрования

SHA - это не шифрование, а хэширование. Хэши с NP-полным поиском коллизий существуют, но имеют другие недостатки.

-- Сб апр 27, 2013 23:57:18 --

AV_77 в сообщении #716428 писал(а):

Хм... это странно. RSA чем не подходит? Или алгоритмы на основе дискретного логарифмирования?

Факторизация и дискретный логарифм не являются NP-полными. Есть сомнения в том, что криптографию с открытым ключом можно построить на NP-полной задаче, см. http://stackoverflow.com/questions/3110 ... -to-defeat

[Esp_]

Xaositect в сообщении #716433 писал(а):

Факторизация и дискретный логарифм не являются NP-полными. Есть сомнения в том, что криптографию с открытым ключом можно построить на NP-полной задаче, см. http://stackoverflow.com/questions/3110 ... -to-defeat

Товарищ написал про NP-hard, а не про NP-complete.

[Xaositect]

Esp_ в сообщении #717698 писал(а):

Товарищ написал про NP-hard, а не про NP-complete.

И NP-трудными они тоже не являются.

[Esp_]

Xaositect в сообщении #717799 писал(а):

И NP-трудными они тоже не являются

Это доказано?

[Xaositect]

Esp_ в сообщении #717844 писал(а):

Это доказано?

Не доказано, извиняюсь. Доказано, что если факторизация является NP-трудной, то NP=coNP.

[Esp_]

Xaositect в сообщении #717847 писал(а):

Не доказано, извиняюсь. Доказано, что если факторизация является NP-трудной, то NP=coNP.

Да, вот о том и речь. Но мнение сообщества в принципе склоняется к тому, что это не NP трудная задача.

[nikvic]

Если не ошибаюсь, для проверки числа на простоту есть полиномиальный алгоритм. Для разложения на множители (пока?) нет.