我最近一直在阅读有关密码学中素因子的一般用途的文章。在我读到的所有地方，它都指出没有在多项式时间（而不是指数时间）中运行的“已发布”算法来查找密钥的主要因素。
如果发现或发布了确实在多项式时间内运行的算法，那么这将如何影响现实世界的计算环境，而不是理论和计算机科学的世界。考虑到我们对密码学的依赖程度会突然停止。
考虑到这一点，如果 P = NP 为真，可能会发生什么，我们在多大程度上取决于它尚未被证实的事实。
我是初学者，所以请原谅我的问题中的任何错误，但我想你会明白我的一般要点。
问问题
3074 次
6 回答
8
考虑到这一点，如果 N = NP 为真，他们会告诉我们吗？
“<em>他们”是谁？如果这是真的，我们会知道的。计算机科学家？那是我们。密码学家和数学家？专业人士？专家？像我们这样的人。互联网用户，甚至 Stack Overflow 的用户。
我们不需要被告知。我们会告诉。
科学和研究不是闭门造车的。如果有人发现 P = NP，这不能保密，仅仅因为研究发表的方式。原则上，每个人都可以进行此类研究。
于 2009-11-12T21:05:19.677 回答
5
这取决于谁发现了它。
与康拉德的说法相反，美国国家安全局和其他在国家资助下研究密码学的组织，在闭门造车的情况下进行研究和科学研究。他们已经“挖掘”了一些重要发现的学术研究人员。最后，在被学术研究人员独立发现后，他们有多年隐瞒密码分析进展的历史。
我不喜欢阴谋论。但是，如果政府没有在分解问题上花费大量“黑”钱，我会感到非常惊讶。如果得到任何结果，它们将被保密。由于未能相互协调以防止恐怖主义，美国的机构受到了很多批评。将 NSA 收集的信息通知 FBI 可能会“过多”地揭示 NSA 的能力。
您可能会发现本次采访中向 Bruce Schneier 提出的第一个问题很有趣。结果是 NSA 总是比学术界有优势，但这种优势正在缩小。
值得一提的是，NSA 建议使用椭圆曲线 Diffie-Hellman 密钥协议，而不是 RSA 加密。他们喜欢较小的钥匙吗？他们期待量子计算吗？或者 … ？
于 2009-11-12T21:34:56.657 回答
5
请记住，不知道因式分解是（并且推测不是）NP 完全的，因此证明用于因式分解的 P 算法并不意味着 P = NP。大概我们可以将我们的加密算法的基础转换为一些 NP 完全问题。
于 2009-11-12T22:16:50.467 回答
4
这是一篇关于P = NPACM 的文章： http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext
从链接：
许多人关注负面因素，即如果 P = NP，那么公钥密码学就变得不可能。没错，但是我们将从 P = NP 中获得的东西将使整个互联网看起来像是历史上的一个脚注。
由于所有 NP 完全优化问题都变得容易，一切都会变得更加高效。所有形式的运输都将得到最佳安排，以更快、更便宜地运送人员和货物。制造商可以改进生产以提高速度并减少浪费。我只是在摸索表面。
鉴于这句话，我相信他们会告诉全世界。
我认为加拿大的一些研究人员（？）很幸运地使用 GPU（或 GPU 集群）分解了大量数据。这并不意味着它们在多项式时间内被分解，但芯片架构更利于分解。
于 2009-11-12T21:12:29.083 回答
3
如果发现了一种真正有效的合数分解算法，我认为最大的直接影响将是电子商务。具体来说，它会停止运行，直到开发出一种不依赖因式分解作为单向函数的加密形式。
在过去的四年里，私营部门对密码学进行了大量研究。与上一个时代相比，这是一个很大的转变，在那个时代，加密货币主要属于军事和秘密政府机构的职权范围。那些秘密机构肯定试图抵制这种变化，但是一旦发现了知识，就很难保密。考虑到这一点，我认为 P = NP 问题的解决方案不会长期保密，尽管它可能在这一领域产生任何影响。潜在的好处将是更广泛的应用。
依赖于量子力学的基础，而传统的公钥密码学依赖于某些数学函数的计算难度，并且不能提供任何窃听的迹象或密钥安全性的保证。
第一个使用该技术的实用网络于 2008 年上线。
于 2009-11-12T21:10:23.783 回答
3
作为旁注，如果您进入量子计算领域，您可以考虑多项式时间。 请参阅 Rob Pike 在他关于量子计算的演讲中的笔记，第 25 页，也称为Shor 算法。
于 2009-11-12T21:39:11.167 回答