Prime Factorization

Question

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

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

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

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

Answer 1

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

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

Кстати, там были некоторые research в quantum cryptography, который

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

first practical network Используя эту технологию, вышли в интернет в 2008 году.

Answer 2

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

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

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

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

Answer 3

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

Из ссылке:

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

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

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

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

Answer 4

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

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

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

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

Для чего стоит, NSA рекомендует использовать соглашение о ключах с шиной Diffie-Hellman с эллиптической кривой, а не RSA-шифрование. Им нравятся меньшие ключи? Стремятся ли они к квантовым вычислениям? Или & hellip; ?

Answer 5

В качестве побочного примечания, если вы войдете в сферу квантовых вычислений, вы можете указать многочленное время. See Rob Pike's notes from his talk on quantum computing, page 25, также известный как Shor's algorithm.

Answer 6

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