logo标签列表

质因数分解

algorithmmathcomputer-scienceprime-factoring
11

最近我一直在阅读关于密码学中使用质因数分解的内容。无论我去哪里阅读，都会说没有“发布”的算法可以在多项式时间（而不是指数时间）内找到密钥的质因数。

如果发现或发布了可以在多项式时间内运行的算法，那么与理论和计算机科学世界相比，这将如何影响实际计算环境？考虑到我们对密码学的依赖程度，世界会突然停滞吗？

有了这个想法，如果P = NP成立，可能会发生什么，我们有多大程度上依赖于它还未得到证明的事实。

作为一个初学者，请原谅我的问题中可能存在的任何错误，但我认为你可以理解我的一般意思。

4
应该设为社区维基页面。或许也适合放在http://mathoverflow.net/ 上面。 - ChristopheD
1
似乎是数学和阴谋论的混合体。（一般来说，任何数学发现都无法保密太久，所以最好放弃阴谋论。） - David Thornley
4
我刚刚浏览了mathoverflow.net，我认为这个问题在那里也不会得到更好的回答。他们似乎更喜欢难题。顺便说一句，你可以在任何你拥有帐户的地方提出这个问题。只要有足够的3K+声望的人或一个版主，就可以将其移动到相应的位置。 - David Thornley
4
@David Thornley: 我们不能让大众知道二的平方根的无理性！ - Bill the Lizard
6
我必须说，我不明白这与编程无关。问题归结为“如果P = NP，哪些现实世界的算法问题会受到影响”，这似乎是一个非常合理的问题。 - mqp
显示剩余4条评论
6个回答
8
考虑到这一点，如果N = NP成立，他们会告诉我们吗？
“他们”是谁？如果真的成立，我们会知道。计算机科学家？那就是我们。密码学家和数学家？专业人士？专家？像我们这样的人。即使是互联网和Stack Overflow的用户也不例外。
我们不需要被告知。我们会“告诉”别人。
科学和研究不是在闭门造车中完成的。如果有人发现P = NP，这是不可能保守秘密的，因为研究成果的发布方式。原则上，每个人都可以访问这样的研究成果。
1
好的人，无论是谁发现的，与恐怖分子和世界末日预言者相对立。我理解你的意思，只是想不出更好的表达方式。如果n = np被证明是真的，考虑到安全性取决于它的程度（目前），这必然是一件好事。 - chrisg
2
+1：他们到底是谁？我一直很好奇。 - S.Lott
6
NSA肯定在闭门里进行研究，但他们是否会发布这样的结果还不确定。我确定它最终会泄露出去，但你永远不知道 =) - Stephen Canon
2
@Stephen, David：即使是美国国家安全局也使用RFP（请求寻求提案书）来设计他们的加密算法，因为他们意识到无法将所有聪明的头脑都封闭在门后。因此，军队和许多大公司都会在闭门造车中进行研究。但我相信所有真正开创性的工作都不能保密。至于NSA领先于公共研究的说法，我不太相信。尽管他们的资源非常丰富，但与“基本上所有其他人”相比，它们太过有限，除了一些很小的问题外，无法与其竞争。 - Konrad Rudolph
6
另一个需要注意的问题是，算法泄漏相对于其他阴谋理论来说更容易。例如，如果军方抓获了外星人，几乎没有任何证据能够说服每个人（即使是物理证据也会被怀疑）。另一方面，如果有人有一个在多项式时间内分解数字的算法，就不需要进一步的证明-它要么有效，要么无效。 - Eclipse
显示剩余3条评论
5
这取决于谁发现它。与Konrad的说法相反，国家赞助的NSA和其他研究密码学的组织在关闭门和枪支后面进行研究和科学，并且他们已经在一些重要的发现上“超越”了已发表的学术研究人员。最后，他们有一个历史，即在学术研究人员独立发现加密分析进展多年之后才公开这些进展。我不是一个信奉阴谋论的人。但如果政府没有在因式分解问题上投入大量“黑色”资金，我会感到非常惊讶。如果获得任何结果，它们将被保密。美国机构未能协调以避免恐怖主义遭到了很多批评。通知FBI由NSA收集的信息可能会揭示有关NSA能力的“过多”信息。您可能会发现Bruce Schneier在此次采访中提出的第一个问题很有趣。总结来说，NSA将始终领先于学术界，但这个优势正在缩小。值得一提的是，NSA建议使用椭圆曲线Diffie-Hellman密钥协商，而不是RSA加密。他们喜欢更小的密钥吗？他们正在展望量子计算吗？还是……？
+1 实际上没错。但我仍然坚持在下面的评论中所说的话。;-) - Konrad Rudolph
我同意这个原则，即长期隐藏数学真理是不可能的。但在此期间，像这样的秘密是任何国家都会小心谨慎地玩弄的有价值的牌。 - erickson
据我所知，NSA发布的椭圆曲线算法被发现存在可能是后门的漏洞，所以他们可能会推动其使用？http://www.schneier.com/essay-198.html - rmeador
1
这不是 EC 密钥协商中的缺陷，而是 NSA 推荐的 RNG 中的缺陷。但这是一个很好的例证; 说明 NSA 可能会选择性地隐藏或揭示密码分析结果，并且学术界通常在几年内独立发现相同的结果。 - erickson
P = NP对计算机科学有着深远的影响，不仅限于密码学。如果被证明，我们将会知道它是当今计算机科学中最大的，如果不是最大的开放问题之一。 - Paul
我们怎么知道呢？我们必须由发现它的人告诉我们。而一些最有可能发现它的人有一些不立即披露的原因。 - erickson
5

请记住，因数分解问题并没有被证明是NP完全的（而且据推测也不是），因此展示一个P算法来解决因数分解问题并不能意味着P=NP。我们可以假设将加密算法的基础切换到某个NP完全问题上。

4
这里有一篇关于ACM的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（或GPU集群）成功分解大型数字。这并不意味着他们在多项式时间内分解了它们，但芯片架构更有利于分解。
1
我不知道其他人是否关注这个问题，这只是我做出的一个观察，我只是试图找出我们实际上在多大程度上依赖于未经证明的n = np事实。 - chrisg
3
如果真正高效的合数因子分解算法被发现，我认为最大的直接影响将会在电子商务领域。具体而言，它将会陷入停滞，直到开发出一种不依赖于因子分解作为单向函数的加密形式。
在过去的四十年里，私营部门进行了大量密码学研究。这是一个很大的转变，之前密码学主要由军方和秘密政府机构掌握。那些机构肯定试图抵制这种变化，但一旦知识被发现，很难保守秘密。考虑到这一点，我认为P=NP问题的解决方案不会长时间保密，尽管它可能在这个领域产生任何影响。潜在的好处将在更广泛的应用领域中得到体现。
顺便说一句，已经有一些关于量子密码学的研究。

与传统的基于某些数学函数的计算困难度的公钥加密不同，它依赖于量子力学的基础，并且无法提供窃听指示或密钥安全保证。

第一个实际使用该技术的网络于2008年上线。

谢谢，这正是我想要的。现实世界有多大程度上依赖它，会发生什么事情呢？我不是阴谋论者，但肯定有人会利用这样的算法制造混乱。 - chrisg
1
你所谈论的只是加密中的公钥（PKI）部分。对称加密算法（例如AES）并不使用质数。但是确实有一些替代的非对称密钥算法，只是它们在商业上并不流行。 - David R Tribble
2
直到开发出一种不依赖于因数分解为单向函数的加密形式，否则它将停滞不前。例如ECC。假设这种因数分解突破并没有解决离散对数问题。 - Steve Jessop
2
-1：它不会停滞不前；存在着一些现有的加密方法，它们不依赖于分解或离散对数的难度（如果分解被破解了，离散对数也几乎肯定会被破解，尽管我不知道是否存在明确的约简）。 - Charles
3
我认为量子计算机将在任何人证明P=NP或证明其不成立之前，使得N=NP的问题过时。 - ldog
@gmatt：不，显然量子计算机无法完成许多有用的NP问题。此外，制造大量量子比特的量子计算机变得非常困难，而且考虑到现代传统计算机可以轻松复制分解15的成就，这一点变得更加困难。我不知道量子计算机是否真正有用。 - David Thornley
@David：真的吗？这让我感到惊讶，我认为NP问题和P问题的类别是这样的，如果你能解决该类别中的任何问题，那么每个其他问题都可以使用相同的算法来解决。 - ldog
gmatt：分解因数问题属于 NP 问题，但也属于 co-NP 问题。这是一个奇怪的问题，这里是维基百科页面链接：http://en.wikipedia.org/wiki/Integer_factorization - agorenst
@ldog：如果您能在多项式时间内解决一个 NP 完全问题，那么您已经解决了所有这样的问题。但是目前并不知道或者相信量子计算机能够解决 任何 NP 完全问题。查阅复杂度类 BQP 以获取有关可以高效解决的信息。Shor 算法和 Grover 算法是最为知名的算法。 - Charles
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接