CODEWITHSUNDEEP
pythonprimality-test
nik panik
nik panik

Reputation: 11

Lucas-Lehmer primality test with python

I wrote the code below, to get the Lucas-Lehmer series up to p, for p the exponent of a Mersenne number. After checking it I found that it doesn't work for some primes p such as 11, 23, 29 etc. Any help will be very valuable!

Here's the code:

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

Upvotes: 1

Views: 5836

Answers (2)

Arca Ege Cengiz
Arca Ege Cengiz

Reputation: 333

Try this:

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

Things to note:

  • You need to call the check_prime function
  • The input to the check_prime function must be a smaller prime number
  • Not all prime numbers produce prime results in the Mersenne sequence.
  • If 2^n - 1 is not prime, it will return -1

I have also cleared the code up a bit and made it easier to read.

Upvotes: 1

Tom Ron
Tom Ron

Reputation: 6181

The Lucas-Lehmer test tests if a Mersenne number is prime. 11 is not a Mersenne number therefore the test fails. Mersennse number is - M_n = 2^n-1.

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

p.s the implementation can be more efficient if you calculate M=(2^p-1) only once

Upvotes: 1

Related Questions