python中512位数字的最大素因数的最快计算

Question

我正在用 python 模拟我的加密方案，我是它的新用户。

p = 512 位数字，我需要计算它的最大素因数，我正在寻找两件事：

1. 处理这个大素因数分解的最快代码
2. 可以将 512 位数字作为输入并可以处理它的代码。

我见过其他语言的不同实现，我的整个代码都是用 python 编写的，这是我陷入困境的最后一点。所以请告诉我 python 中是否有任何实现。

请简单地解释一下，因为我是 python 的新用户，

抱歉英语不好。

编辑（取自下面OP的答案）：

#!/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

对于基于 Python 的解决方案，您可能需要查看 pyecm 在还安装了 gmpy 的系统上，pyecm 发现以下因子：

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

仍然有一个 98 位未分解的复合数

60252507174568243758911 151187828438446814447653986842279796823262165159406500174226172705680274911

使用 ECM 分解此剩余复合材料可能不切实际。

编辑：几个小时后，剩下的因子是

6060517860310398033985611921721

和

9941808367425935774306988776021629111399536914790551022447994642391

Answer 2

对于大数来说，这应该比简单的方法更合适（尽管这种数字处理每个纯Python实现都需要一段时间）：Pollard Rho 素数分解。

Answer 3

如果您可以安装扩展程序，gmpy 会有所帮助 - 请参阅我对此的回答所以问题，特别是 def prime_factors(x ) 我在那里展示的代码中的函数。

在纯Python（不允许任何扩展）中，它有点难，而且慢很多，请参阅代码 这里（但是当它在巨大的数字上运行时不要屏住呼吸；-）。

Answer 4

('''==============================================================================='''
>        '''              CALCULATE  HIGHEST PRIME
> FACTOR                                  '''
>
> '''===============================================================================''')
>
> #!/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”但是
延伸至
（1090261099132914243663055115810860896506281174639257767545600484549911304430471090261099132914243663055115810860896506281 17463925776754560048454991130443047)
让蟒蛇发疯。有没有办法像上面一样，我可以拥有
很快就计算出来了。