python - 使用 Python 的 Lucas-Lehmer 测试不适用于大量数据

Question

我正在尝试编写一个函数，该函数应该接受梅森数并使用 Lucas-Lehmer 素数测试返回它是否是素数。我正在尝试返回 Lucas-Lehmer 序列中生成的最后一个数字，如果它是质数，它应该是 0

我编写了以下函数来执行上述操作

def lucas_lehmer_modified(p):
   M=2**p-1
   for i in range (0,p-1):
     if i == 0:
       x = 4
     else : 
        x = (prev**2-2)%(M)
     prev=x
   return x

我的问题是此代码适用于小数，例如127但不适用于大数，2305843009213693951例如524287. 我的 Python Jupyter 笔记本挂断了。关于如何获得一个函数的任何建议，该函数将梅森素数作为输入并使用 Lucas Lehmer 测试返回它是否是素数。我需要让它至少工作2^65-1

Answer 1

我从维基百科条目的伪代码中编写了 Lucas Lehmer 测试，这是我想出的（p 是 mersenne 幂数）：

def LucasLehmer(p):
   if p == 2:
     return True
   s = 4
   M = pow(2, p) - 1
   for x in range (1, (p-2)+1):
      s = ((s * s) - 2) % M
   if s == 0: return True
   else: return False

还有一些答案：

In [388]: LucasLehmer(9689)                                                                                                                                                                     
Out[388]: True

In [389]: LucasLehmer(19937)                                                                                                                                                                    
Out[389]: True

In [390]: LucasLehmer(500)                                                                                                                                                                      
Out[390]: False