Python中512位数最大质因数的最快计算方法

Question

我正在用Python模拟我的加密方案，我是新手。

p是一个512位的数字，我需要计算它最大的质因数，我在寻找两个东西：

1. 处理这个大质因数分解的最快代码
2. 能够接受512位数字作为输入并处理它的代码。

我在其他语言中见过不同的实现，但我的整个代码都是用Python写的，这也是我卡住的最后一步。所以请告诉我有没有Python的实现。

请用简单的方式解释，因为我对Python还不太熟悉。

抱歉我的英语不好。

编辑（摘自楼主的回答）：

#!/usr/bin/env python
def highest_prime_factor(n):
   if isprime(n):
      return n
   for x in xrange(2,n ** 0.5 + 1):
      if not n % x:
         return highest_prime_factor(n/x)

def isprime(n):
   for x in xrange(2,n ** 0.5 + 1):
      if not n % x:
         return False
   return True

if  __name__ == "__main__":
   import time
   start = time.time()
   print highest_prime_factor(1238162376372637826)
   print time.time() - start

上面的代码可以工作（虽然有点慢），对于“1238162376372637826”这个数字可以处理，但如果扩展到

10902610991329142436630551158108608965062811746392 57767545600484549911304430471090261099132914243663 05511581086089650628117463925776754560048454991130443047

就会让Python崩溃。有没有办法像上面那样，让它能在短时间内计算出来？

Answer 1

如果你可以安装一个扩展，gmpy 会很有帮助——你可以看看我对这个 SO问题 的回答，特别是我在那里的代码中提到的 def prime_factors(x) 函数。

如果只用纯Python（不允许使用任何扩展），那就稍微难一些，而且速度会慢很多，看看这个代码 这里 的例子（不过在处理大数字时可别指望它能快;-）。

Answer 2

对于处理大数字来说，这种方法应该比简单的方法更合适（不过用纯Python来做这种计算，速度都会比较慢）：Pollard Rho质因数分解。

Answer 3

如果你想用Python来解决这个问题，可以看看pyecm这个工具。在一个安装了gmpy的系统上，pyecm找到了以下几个因子：

101, 521, 3121, 9901, 36479, 300623, 53397071018461, 1900381976777332243781

不过，还有一个98位的合成数没有被分解：

60252507174568243758911151187828438446814447653986842279796823262165159406500174226172705680274911

用ECM方法来分解这个剩下的合成数可能不太实际。

补充：经过几个小时，剩下的因子是

6060517860310398033985611921721

还有

9941808367425935774306988776021629111399536914790551022447994642391