64bit整数快速因子分解算法

mathe

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

wayne

前几天我还看到了有人用单台PC机2小时破解了128位的GSM加密
也是大数分解吗

KeyTo9_Fans

大概是的吧。

等我的代码优化得足够好之后，我想试着将其运算范围改编成128bit的。

即使用两个64bit的整数拼起来表示一个128bit的整数。

看看对于128bit的整数，这个程序的分解效率如何。

mathe

对于128比特的,rho算法会太慢了。因为其复杂度在$sqrt(p)$,p为待分解数的因子

风云剑

GSM加密算法A5，网上有不少介绍。我没研究过，感觉和大数分解不是很相关。
后来好像有升级到A8之类的。

victoria0217

各位大牛们能帮助小妹质因数分解 n= 100671626569831775256297934351678351497999091707202899105791276287616380639321439109716332731398235408349245699480491937721766867821439179283873
么？这是RSA的Key，教授让我们找到那两个质数……超级感谢啊

mathe

这个整数可不小，看着不像是作业。

medie2005

你给你教授一个144位的p*q形式的合数，在一个星期内，他也不一定能分解掉。
你教授不会是想让你们去破解RSA吧？

KeyTo9_Fans

别着急。

我有空rho一下。

rho不出来再投诉你们的教授。

#####

囧rz...

我的第200贴竟然是这样的烂贴子

#####

to楼下:

我是指望第一个因子$p$比较小，然后用$\sqrt p$的时间搞定它。

medie2005

pollard rho方法对RSA是无助益的。