可能的重复：
使用 gmp 有效地分解一个大数
我知道我已经发布了它，但是人们误解了我的意思，直到我修复它之前，帖子都死了。
我需要的是一种使用 C++ 和 GMP（Gnu Multiple Precession lib）或更少优选任何其他方式来有效分解（找到一个数字的素数）大数（可能达到 2048 位）的方法。
这些数字实际上是随机的，因此很难考虑的可能性很小，即使这个数字很难考虑，我也可以重新计算这个数字（虽然不能选择）。
我该怎么做？
问问题
1807 次
7 回答
2
没有有效的方法（可能）。这个假设是现代密码学的基础。
于 2010-12-05T14:19:35.023 回答
1
于 2010-12-05T14:23:08.480 回答
1
为什么你认为它不难分解？是的，会有一些小因素。但是其余的将足够大，以至于通常需要一些认真的工作才能考虑。
我建议通过一些小的素数进行尝试划分，以将小鱼从池塘中取出。然后你可能会尝试 Pollard 的 rho 方法，但我怀疑它是否有机会处理这么多位的数字。最好是二次筛。
于 2010-12-05T14:31:06.050 回答
0
一种有效地执行此操作的方法将破坏许多当前使用的加密算法。
这是一个NPC问题，所以......
于 2010-12-05T14:19:51.653 回答
0
你试过二次筛还是一般数域筛？（QS 更简单，更容易实现，GNFS 对于非常大的数字更快，但您的数字可能不够大，GNFS 比 QS 快得多）
编辑：根据Eric Landquist 的一篇论文，QS 和 GNFS 之间的交叉点约为 110 位 = 约 365 位。
于 2010-12-05T14:19:53.903 回答
0
如果我没有遗漏任何东西这被称为“困难”问题。http://en.wikipedia.org/wiki/Integer_factorization。即目前是不可能的。
于 2010-12-05T14:20:37.430 回答
0
没有已知的方法可以有效地分解大数。有关原因和最新技术的讨论，请参见Wikipedia。
正如评论所指出的，这个问题的困难是许多现代密码学的基础，特别是公钥加密。
您可以做的是存储一个小素数表，并通过该表将您的大数除以每个候选素数。如果数字“太难”（即您用完了小素数），则重新滚动。
于 2010-12-05T14:20:53.523 回答