2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 NP-полные задачи и криптография
Сообщение27.04.2013, 10:11 
Заслуженный участник
Аватара пользователя


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


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

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

 Профиль  
                  
 
 Re: Чем вообще занимаются современные математики?
Сообщение27.04.2013, 13:29 
Заслуженный участник
Аватара пользователя


08/11/11
5940
Munin в сообщении #716164 писал(а):
g______d в сообщении #716119 писал(а):
(речь о P=NP) Прямых практических приложений у этой задачи не будет.

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


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

 Профиль  
                  
 
 Re: Чем вообще занимаются современные математики?
Сообщение27.04.2013, 19:54 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Чем вообще занимаются современные математики?
Сообщение27.04.2013, 19:57 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Munin в сообщении #716352 писал(а):
Кстати, SHA-256, насколько я знаю, не на задаче коммивояжёра основана: если задачу коммивояжёра и "взломают", на другие $NP$-задачи распространить это может потребоваться ещё лет 50.
Нет, там все сводимости от одной задачи к другой достаточно простые, и по времени как правило не больше $n^3$

 Профиль  
                  
 
 Re: Чем вообще занимаются современные математики?
Сообщение27.04.2013, 22:18 
Заслуженный участник
Аватара пользователя


30/01/06
72407
Xaositect в сообщении #716356 писал(а):
Нет, там все сводимости от одной задачи к другой достаточно простые

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

 Профиль  
                  
 
 Re: Чем вообще занимаются современные математики?
Сообщение27.04.2013, 22:28 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Чем вообще занимаются современные математики?
Сообщение27.04.2013, 22:40 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Чем вообще занимаются современные математики?
Сообщение27.04.2013, 22:44 
Заслуженный участник


11/11/07
1198
Москва
g______d в сообщении #716423 писал(а):
Я вообще не нашел ни одного алгоритма шифрования, взлом которого NP-сложен.

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

 Профиль  
                  
 
 Re: Чем вообще занимаются современные математики?
Сообщение27.04.2013, 22:55 
Заслуженный участник
Аватара пользователя


06/10/08
6422
g______d в сообщении #716423 писал(а):
алгоритма шифрования
SHA - это не шифрование, а хэширование. Хэши с NP-полным поиском коллизий существуют, но имеют другие недостатки.

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

AV_77 в сообщении #716428 писал(а):
Хм... это странно. RSA чем не подходит? Или алгоритмы на основе дискретного логарифмирования?
Факторизация и дискретный логарифм не являются NP-полными. Есть сомнения в том, что криптографию с открытым ключом можно построить на NP-полной задаче, см. http://stackoverflow.com/questions/3110 ... -to-defeat

 Профиль  
                  
 
 Re: Чем вообще занимаются современные математики?
Сообщение30.04.2013, 14:52 


22/01/11
309
Xaositect в сообщении #716433 писал(а):
Факторизация и дискретный логарифм не являются NP-полными. Есть сомнения в том, что криптографию с открытым ключом можно построить на NP-полной задаче, см. http://stackoverflow.com/questions/3110 ... -to-defeat


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

 Профиль  
                  
 
 Re: Чем вообще занимаются современные математики?
Сообщение30.04.2013, 16:00 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Esp_ в сообщении #717698 писал(а):
Товарищ написал про NP-hard, а не про NP-complete.
И NP-трудными они тоже не являются.

 Профиль  
                  
 
 Re: NP-полные задачи и криптография
Сообщение30.04.2013, 17:51 


22/01/11
309
Xaositect в сообщении #717799 писал(а):
И NP-трудными они тоже не являются


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

 Профиль  
                  
 
 Re: NP-полные задачи и криптография
Сообщение30.04.2013, 17:58 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Esp_ в сообщении #717844 писал(а):
Это доказано?
Не доказано, извиняюсь. Доказано, что если факторизация является NP-трудной, то NP=coNP.

 Профиль  
                  
 
 Re: NP-полные задачи и криптография
Сообщение01.05.2013, 11:46 


22/01/11
309
Xaositect в сообщении #717847 писал(а):
Не доказано, извиняюсь. Доказано, что если факторизация является NP-трудной, то NP=coNP.


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

 Профиль  
                  
 
 Re: NP-полные задачи и криптография
Сообщение01.05.2013, 12:21 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

Модератор: Модераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group