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

Question

我正在尝试写一个函数，它应该接受一个Mersenne数，并使用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测试获得一个函数，该函数接受一个Mersenne素数作为输入，并返回它是否为质数，有什么建议吗？我需要让它至少为2^65-1工作

Answer 1

我用维基百科条目中的psuedocode写了一个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