质因数分解
我最近一直在阅读有关密码学中质因数的一般用途的文章。在我读过的所有地方，它都指出不存在以多项式时间（而不是指数时间）运行的“已发布”算法来查找密钥的素因数。
如果发现或发布了一种确实在多项式时间内运行的算法，那么这将如何影响现实世界的计算环境，而不是理论和计算机科学的世界。考虑到我们对密码学的依赖程度，这种情况会突然停止。
考虑到这一点，如果 P = NP 为真，可能会发生什么，我们在多大程度上取决于它尚未得到证实的事实。
我是初学者，所以请原谅我的问题中的任何错误，但我认为您会明白我的一般要点。
I have recently been reading about the general use of prime factors within cryptography. Everywhere i read, it states that there is no 'PUBLISHED' algorithm which operates in polynomial time (as opposed to exponential time), to find the prime factors of a key.
If an algorithm was discovered or published which did operate in polynomial time, then how would this impact in the real world computing environment as opposed to the world of theory and computer science. Considering the extent we depend on cryptography would the would suddenly come to halt.
With this in mind if P = NP is true, what might happen, how much do we depend on the fact that it is yet uproved.
I'm a beginner so please forgive any mistakes in my question, but i think you'll get my general gist.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
“他们”是谁？如果这是真的，我们就会知道。计算机科学家？那就是我们。密码学家和数学家？专业人士？专家们？像我们这样的人。互联网用户，甚至 Stack Overflow 的用户。
我们不需要被告知。我们会告诉。
科学研究并不是闭门进行的。如果有人发现 P = NP，这不能保密，仅仅是因为研究发表的方式。原则上，每个人都可以访问此类研究。
Who are “they”? If it were true, we would know. The computer scientists? That’s us. The cryptographers and mathematicians? The professionals? The experts? People like us. Users of the Internet, even of Stack Overflow.
We wouldn’t need being told. We’d tell.
Science and research isn’t done behind closed doors. If someone finds out that P = NP, this couldn’t be kept secret, simply because of the way that research is published. In principle, everyone has access to such research.
这取决于谁发现它。
与康拉德的说法相反，美国国家安全局和其他在国家资助下研究密码学的组织是在闭门造车的情况下进行研究和科学研究的——而且还使用枪支。他们还“挖”出了学术研究人员发表的一些重要发现。最后，在学术研究人员独立发现密码分析进展后，他们有多年保留这些进展的历史。
我不太热衷于阴谋论。但如果政府没有在分解问题上花费大量“黑”钱，我会感到非常惊讶。如果获得任何结果，它们将被保密。美国各机构因未能相互协调以避免恐怖主义而受到许多批评。向联邦调查局通报国家安全局收集的信息可能会“过多地”透露国家安全局的能力。
您可能会在本次采访中找到向 Bruce Schneier 提出的第一个问题< /a> 有趣。结果是国家安全局始终比学术界拥有优势，但这种优势正在缩小。
无论如何，NSA 建议使用椭圆曲线 Diffie-Hellman 密钥协议，而不是 RSA 加密。他们喜欢较小的钥匙吗？他们期待量子计算吗？或者 … ？
It depends on who discovers it.
NSA and other organizations that research cryptography under state sponsorship, contrary to Konrad's assertion, do research and science behind closed doors—and guns. And they have "scooped" published academic researchers on some important discoveries. Finally, they have a history of withholding cryptanalytic advances for years after they are independently discovered by academic researchers.
I'm not big into conspiracy theories. But I'd be very surprised if a lot of "black" money hasn't been spent by governments on the factorization problem. And if any results are obtained, they would be kept secret. A lot of criticism has been leveled at agencies in the U.S. for failing to coordinate with each other to avert terrorism. It might be that notifying the FBI of information gathered by the NSA would reveal "too much" about the NSA's capabilities.
You might find the first question posed to Bruce Schneier in this interview interesting. The upshot is that NSA will always have an edge over academia, but that margin is shrinking.
For what it is worth, the NSA recommends the use of elliptic curve Diffie-Hellman key agreement, not RSA encryption. Do they like the smaller keys? Are they looking ahead to quantum computing? Or … ?
请记住，因式分解未知（并且推测不是）NP 完全的，因此证明用于因式分解的 P 算法不会意味着 P=NP。想必我们可以将加密算法的基础转向一些 NP 完全问题。
Keep in mind that factoring is not known to be (and is conjectured not to be) NP-complete, thus demonstrating a P algorithm for factoring will not imply P=NP. Presumably we could switch the foundation of our encryption algorithms to some NP-complete problem instead.
以下是 ACM 中有关
P = NP的文章：http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-问题/全文来自链接：
鉴于这句话，我确信他们会告诉全世界。
我认为加拿大（？）的一些研究人员很幸运地使用 GPU（或 GPU 集群）对大数进行因式分解。这并不意味着它们在多项式时间内被分解，但芯片架构更有利于分解。
Here's an article about
P = NPfrom the ACM: http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltextFrom the link:
Given this quote, I'm sure they would tell the world.
I think there were researchers in Canada(?) that were having good luck factoring large numbers with GPUs (or clusters of GPUs). It doesn't mean they were factored in polynomial time but the chip architecture was more favorable to factorization.
如果发现一种真正有效的合数因式分解算法，我认为最大的直接影响将是对电子商务。具体来说，它会逐渐停止，直到开发出一种不依赖于分解作为单向函数的加密形式。
在过去的四十年里，私营部门对密码学进行了大量研究。与上一个时代相比，这是一个重大转变，在上一个时代，加密货币主要属于军事和秘密政府机构的职权范围。那些秘密机构肯定试图抵制这种变化，但一旦发现知识，就很难将其保密。考虑到这一点，我认为 P = NP 问题的解决方案不会长期成为秘密，尽管它可能会在这一领域产生任何影响。潜在的好处将涉及更广泛的应用。
顺便说一句，已经有一些研究 量子密码学，
使用该技术的第一个实用网络于 2008 年上线。
If a truly efficient algorithm for factoring composite numbers was discovered, I think the biggest immediate impact would be on e-commerce. Specifically, it would grind to a halt until a form of encryption was developed that doesn't rely on factoring being a one-way function.
There has been a lot of research into cryptography in the private sector for the past four decades. This was a big switch from the previous era, where crypto was largely in the purview of the military and secret government agencies. Those secret agencies definitely tried to resist this change, but once knowledge is discovered, it's very hard to keep it under wraps. With that in mind, I don't think a solution to the P = NP problem would remain a secret for long, despite any ramifications it might have in this one area. The potential benefits would be in a much wider range of applications.
Incidentally, there has been some research into quantum cryptography, which
The first practical network using this technology went online in 2008.
附带说明一下，如果您进入量子计算领域，您可以考虑多项式时间。 请参阅 Rob Pike 在量子计算演讲中的笔记，第 25 页，也称为 Shor 算法。
As a side note, if you enter into the realm of quantum computing, you can factor in polynomial time. See Rob Pike's notes from his talk on quantum computing, page 25, also known as Shor's algorithm.