用python进行Lucas-Lehmer素性检验

Question

我写了下面的代码，使Lucas-Lehmer级数达到p，p是Mersenne数的指数。在检查之后，我发现它对一些素数p不起作用，比如11，23，29等等。任何帮助都是非常有价值的！

代码如下：

def ll_series (p):
    ll_list=[4]
    print 4
    for i in range(1, p+1):
        ll_list.append((ll_list[i-1]**2 - 2) % (2**p-1))
        print(ll_list[i])
    return ll_list

Answer 1

Lucas-Lehmer检验检验一个Mersenne数是否为素数。11不是Mersenne数字，因此测试失败。梅森斯数是- M_n = 2^n-1。

http://mathworld.wolfram.com/MersenneNumber.html

备注:如果只计算一次M=(2^p-1)，实现效率会更高

Answer 2

试试这个：

lucas_lehmer = [4]

def mersenne(n):
    return (2 ** n) - 1

def ll(n):
    global lucas_lehmer
    if len(lucas_lehmer) < n:
        for num in range(n-1):
            lucas_lehmer.append(lucas_lehmer[-1] ** 2 - 2)
    return lucas_lehmer[n-1]

def check_prime(n):
    m = mersenne(n)
    if ll(n - 1) % m == 0:
        return m
    else:
        return -1

注意事项：

• 您需要调用check_prime函数
• check_prime函数的输入必须是一个较小的质数
• 并非所有质数都会在梅森序列中产生质数结果。
• 如果2^n - 1不是质数，它将返回-1

我还对代码进行了一些清理，使其更易于阅读。