Простые множители

Question

Недавно я читал об общем использовании основных факторов в криптографии. Везде, где я читаю, говорится, что не существует «ОПУБЛИКОВАННОГО» алгоритма, который работает за полиномиальное время (в отличие от экспоненциального), чтобы найти основные факторы ключа.

Если был обнаружен или опубликован алгоритм, который работал за полиномиальное время, то как это отразилось бы на реальной вычислительной среде в отличие от мира теории и информатики. Учитывая степень нашей зависимости от криптографии, она внезапно остановится.

Имея это в виду, если P = NP истинно, что может случиться, насколько мы зависим от того факта, что оно все еще изменено.

Я новичок, поэтому прошу прощения за любые ошибки в моем вопросе, но я думаю, что вы получите мой общий смысл.

Answer 1

Имея это в виду, если N = NP истинно, они когда-нибудь скажут нам.

Кто такие « они »? Если бы это было правдой, мы бы знали бы. Компьютерные ученые? Это мы. Криптографы и математики? Профессионалы? Эксперты? Люди, как мы. Пользователи интернета, даже Stack Overflow.

Нам не нужно было бы говорить. Мы скажем .

Наука и исследования не проводятся за закрытыми дверями. Если кто-то узнает, что P = NP, это не может быть засекречено, просто из-за способа публикации исследования. В принципе, каждый имеет доступ к таким исследованиям.

Answer 2

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

Answer 3

Зависит от того, кто его обнаружит.

АНБ и другие организации, которые исследуют криптографию при государственном спонсорстве, вопреки утверждению Конрада, занимаются исследованиями и наукой за закрытыми дверями - и оружием. И они «выкопали» опубликованные научные исследования некоторых важных открытий. И наконец, у них есть история, в которой многие годы они скрывали криптоаналитические достижения после того, как они были независимо обнаружены учеными.

Я не большой в теории заговора. Но я был бы очень удивлен, если бы правительства не потратили много «черных» денег на проблему факторизации. И если будут получены какие-либо результаты, они будут храниться в секрете. Агентства в США подверглись большой критике за неспособность координировать свои действия с целью предотвращения терроризма. Возможно, что уведомление ФБР об информации, собранной АНБ, может раскрыть «слишком много» о возможностях АНБ.

Вы могли бы найти первый вопрос, заданный Брюсу Шнайеру в этом интервью интересным. В результате АНБ всегда будет иметь преимущество перед научными кругами, но эта разница сокращается.

Для чего это стоит, АНБ рекомендует использовать соглашение о ключе Диффи-Хеллмана с эллиптической кривой, а не шифрование RSA. Им нравятся меньшие ключи? Они с нетерпением ждут квантовых вычислений? Или & hellip;

Answer 4

Вот статья о P = NP из ACM: http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext

Из ссылки:

Многие фокусируются на негативе, если Р = NP, тогда криптография с открытым ключом становится невозможной. Правда, но что мы получит от P = NP сделает Весь интернет похож на сноску в история.

Так как все NP-полные оптимизации проблемы становятся легкими, все будет быть намного более эффективным. Транспорт все формы будут запланированы оптимально перемещать людей и товары вокруг быстрее и дешевле. Производители могут улучшить свои производство для увеличения скорости и создавать меньше отходов. И я просто царапин на поверхности.

Учитывая эту цитату, я уверен, они скажут миру.

Я думаю, что в Канаде (?) Были исследователи, которым повезло, учитывая большое количество GPU (или кластеров GPU). Это не означает, что они были учтены за полиномиальное время, но архитектура чипа была более благоприятной для факторизации.

Answer 5

В качестве примечания, если вы войдете в сферу квантовых вычислений, вы можете учесть полиномиальное время. См. Заметки Роба Пайка из его доклада о квантовых вычислениях, стр. 25 , также известного как алгоритм Шора .

Answer 6

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

За последние четыре десятилетия было проведено много исследований в области криптографии в частном секторе. Это был большой переход от предыдущей эпохи, когда криптография была в основном в компетенции военных и секретных правительственных учреждений. Эти секретные агентства определенно пытались противостоять этому изменению, но как только знания обнаружены, очень трудно держать их в секрете. Имея это в виду, я не думаю, что решение проблемы P = NP останется секретом надолго, несмотря на любые последствия, которые он может иметь в этой области. Потенциальные преимущества будут в гораздо более широком диапазоне применений.

Кстати, было проведено исследование в квантовой криптографии , которая

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

Первая практическая сеть , использующая эту технологию, была запущена в эксплуатацию в 2008 году.