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

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

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

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

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

Ответ 1

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

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

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

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

первая практическая сеть с использованием этой технологии вышла в интернет в 2008 году.

Ответ 2

С учетом этого, если N = NP истинно, они когда-нибудь расскажут нам.

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

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

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

Ответ 3

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

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

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

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

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

Ответ 4

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

Ответ 5

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

Из ссылки:

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

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

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

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

Ответ 6

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