1

我正在用 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

让蟒蛇发疯。有什么办法可以像上面一样,我可以立即计算出来吗?

4

4 回答 4

3

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

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

还有一个 98 位未分解的复合:

60252507174568243758911151187828438446814447653986842279796823262165159406500174226172705680274911

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

编辑:几个小时后,剩下的因素是

6060517860310398033985611921721

9941808367425935774306988776021629111399536914790551022447994642391

于 2010-03-09T06:36:46.977 回答
2

这应该比处理大数的简单方法更合适(尽管使用这种数字处理每个纯 Python 实现都需要一段时间):Pollard Rho prime factorization

于 2010-03-08T18:47:45.177 回答
1

如果您可以安装扩展程序,gmpy会有所帮助——请参阅我对这个SO 问题的回答,特别是def prime_factors(x)我在那里显示的代码中的功能。

在纯 Python 中(不允许任何扩展),它有点难而且慢得多,例如,请参见此处的代码(但不要在它运行在你的大量数字上时屏住呼吸;-)。

于 2010-03-08T18:29:01.410 回答
-1
('''==============================================================================='''
>        '''              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

the code works with a bit of delay on the number : "1238162376372637826" but extending it to (109026109913291424366305511581086089650628117463925776754560048454991130443047109026109913291424366305511581086089650628117463925776754560048454991130443047) makes python go crazy. 有没有像上面这样的方法,我可以立即计算出来。

于 2010-03-08T19:24:36.863 回答