A further improvement was made by Pollard and Brent. They observed that if gcd(a,n) > 1, then also gcd(ab,n) > 1 for any positive integer b. In particular, instead of computing gcd( | x − y | ,n) at every step, it suffices to define z as the product of 100 consecutive | x − y | terms modulo n, and then compute a single gcd(z,n). A major speed up results as 100 gcd steps are replaced with 99 multiplications modulo n and a single gcd. Occasionally it may cause the algorithm to fail by introducing repeated factor, for instance when n is a square. But it then suffices to go back to the previous gcd term, where gcd(z,n) = 1, and use the regular Rho algorithm from there.
http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
前几天我还看到了有人用单台PC机2小时破解了128位的GSM加密
也是大数分解吗
大概是的吧。
等我的代码优化得足够好之后，我想试着将其运算范围改编成128bit的。
即使用两个64bit的整数拼起来表示一个128bit的整数。
看看对于128bit的整数，这个程序的分解效率如何。
对于128比特的,rho算法会太慢了。因为其复杂度在$sqrt(p)$,p为待分解数的因子
GSM加密算法A5，网上有不少介绍。我没研究过，感觉和大数分解不是很相关。
后来好像有升级到A8之类的。
各位大牛们能帮助小妹质因数分解 n= 100671626569831775256297934351678351497999091707202899105791276287616380639321439109716332731398235408349245699480491937721766867821439179283873
么？这是RSA的Key，教授让我们找到那两个质数……超级感谢啊
这个整数可不小，看着不像是作业。
你给你教授一个144位的p*q形式的合数，在一个星期内，他也不一定能分解掉。
你教授不会是想让你们去破解RSA吧？
本帖最后由 KeyTo9_Fans 于 2010-2-11 14:15 编辑
别着急。
我有空rho一下。
rho不出来再投诉你们的教授。
#####
囧rz...
我的第200贴竟然是这样的烂贴子:'(
#####
to楼下:
我是指望第一个因子$p$比较小，然后用$\sqrt p$的时间搞定它。
pollard rho方法对RSA是无助益的。