python - 使用 python 的 Lucas-Lehmer 素性测试

Question

我编写了下面的代码，以使 Lucas-Lehmer 级数达到 p，因为 p 是梅森数的指数。检查后我发现它不适用于某些素数 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 = [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

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

Answer 2

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

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

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