对大数进行因式分解
可能的重复：
使用 gmp 高效分解大数
我知道我已经发布了它，但人们误解了我的意思，直到我修复它之后，该帖子才被删除。
我需要的是一种使用 C++ 和 GMP（Gnu Multiple Precession lib）或不太优选的任何其他方式有效因式分解（查找数字的质因数）大数（可能达到 2048 位）的方法。
这些数字实际上是随机的，所以几乎不可能很难分解，即使数字很难分解，我也可以重新滚动该数字（但不能选择）。
我该怎么做？
Possible Duplicate:
Factor a large number efficiently with gmp
I know I already posted it, but people misunderstood what I meant, and until I fixed it the post died.
What I need is a way to efficiently factor(find prime factors of a number) large numbers(may get to 2048 bits) using C++ and GMP(Gnu Multiple Precession lib) or less preferably any other way.
The numbers are practically random so there is little chance it will be hard to factor, and even if the number is hard to factor, I can re-roll the number(can't choose though).
How do I do it?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
没有有效的方法（可能）。这个假设是现代密码学的基础。
There is no efficient way (probably). This assumption is the basis of modern cryptography.
http://en.wikipedia.org/wiki/General_number_field_sieve
祝你好运！
http://en.wikipedia.org/wiki/General_number_field_sieve
Good luck!
为什么你认为分解因子并不困难？是的，会有一些小因素。但其余部分的数量足够大，通常需要进行一些认真的工作才能进行分解。
我建议用一些小质数进行试除，以将小鱼从池塘中取出。那么您可以尝试 Pollard 的 rho 方法，但我怀疑它对于具有那么多位的数字是否有机会。更好的是二次筛。
Why do you think it will not be hard to factor? Yes, there will be some small factors. But the rest will be large enough in a number of that size that it will often take some serious work to factor.
I would suggest trial divisions by some small primes to get the small fish out of the pond. Then you might try Pollard's rho method, but I doubt it has a chance on numbers with that many bits. Better would be a quadratic sieve.
您是否尝试过二次筛或通用数域筛？ （QS 更简单且更容易实现，对于非常大的数字，GNFS 更快，但您的数字可能不足以让 GNFS 比 QS 快得多）
编辑：根据 Eric Landquist 的论文，QS 和 GNFS 之间的交叉点约为 110 位数字 = 约 365 位。
Have you tried the quadratic sieve or the general number field sieve? (QS simpler and easier to implement, GNFS faster for very large numbers, but your numbers may not be large enough for GNFS to be much faster than QS)
edit: According to a paper by Eric Landquist, the crossover point between QS and GNFS is about 110 digits = approx 365 bits.
如果我没有遗漏任何东西，这被认为是一个“困难”的问题。 http://en.wikipedia.org/wiki/Integer_factorization。即目前这是不可能的。
If i am not missing anything This is known to be a "difficult" problem. http://en.wikipedia.org/wiki/Integer_factorization. i.e. it is currently impossible.
没有已知的方法可以有效地分解大数。请参阅 Wikipedia 了解原因和最新技术的讨论。
正如评论所指出的，这个问题的难度是许多现代密码学的基础，特别是公钥加密。
您可以做的是存储一个小素数表，并通过该表将您的大数除以每个候选素数。如果数字“太难”（即你用完了小素数），则重新滚动。
There is no known way to efficiently factor large numbers. See Wikipedia for a discussion of why and the state of the art.
As the comments have pointed out, the difficulty of this problem is the basis of much modern cryptography, particularly public-key encryption.
What you could do is store a table of small primes and work through that table dividing your large number by each candidate prime as it goes. If the number is "too hard" (i.e. you run out of small primes) then re-roll.
有效地做到这一点的方法将打破许多当前使用的加密算法。
这是一个NPC问题，所以......
A way of doing this efficiently will break many the currently in use encryption algorithms.
This is an NPC problem, so....