Test for the Primality of Mersenne numbers

Question

please assist in solving this problem;

For a given Mersenne number with exponent p, the number is prime if the Lucas-Lehmer series is 0 at position p - 2. Write a function that tests if a Mersenne number with exponent p is prime. Test if the Mersenne numbers with prime p between 3 and 65 are prime. Your final answer should be a list of tuples consisting of (Mersenne exponent, 0) or (1) for each Mersenne number you test, where 0 and 1 are replacements for 'False' and 'True' respectively. Shown below is my attempted solution

#function to define a mersenne number
def mersenne_number(p):
    return 2**p - 1

#function to generate the Lucas-Lehmer sequence
def lucas_lehmer(p):
    ll_seq = [4]
    if p > 2:
        for i in range(1, (p - 2) + 1):
            n_i = (ll_seq[i-1] ** 2 - 2)%(2**p - 1)
            ll_seq.append(n_i)
    return ll_seq

#To generate a list of Tuples consisting of (mersenne exponents, 1 or 0), 1 and 0 represent True and False respectively.
mersenne_primes = []

def ll_prime(num1, num2):
    for p in range(3, 65):
        if lucas_lehmer(p)[-1] == 0:
            mersenne_primes.append((p, 1))
        else:
            mersenne_primes.append((p, 0))

    print(mersenne_primes)

I am getting a wrong output at this stage. The function is returning prime mersenne exponents as not prime meaning 0.

You've already asked this question: [Test for Primality of Mersenne Numbers](https://stackoverflow.com/questions/61902200/test-for-primality-of-mersenne-numbers) — Welbog, May 21 '20 at 16:47

score 0 · Answer 1 · answered Jun 21 '20 at 00:04

I implemented the Lucas Lehmer test from the psuedocode on it's wikipedia page here:

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

for x in range(2,10000): 
   if LucasLehmer(x): 
      print(f"2**{x}-1 is Prime") 
                                                                                                                                                           
2**2-1 is Prime
2**3-1 is Prime
2**5-1 is Prime
2**7-1 is Prime
2**13-1 is Prime
2**17-1 is Prime
2**19-1 is Prime
2**31-1 is Prime
2**61-1 is Prime
2**89-1 is Prime
2**107-1 is Prime
2**127-1 is Prime
2**521-1 is Prime
2**607-1 is Prime
2**1279-1 is Prime
2**2203-1 is Prime
2**2281-1 is Prime

I also changed the math around to make it a factorization engine, if your interested in using it for factoring here it is:

import math

def PrimeFinderLucasLehmer4(N):
   p = 1<<N.bit_length()-1
   if N == 2:
     return 2
   if N == 3:
     return 3
   s = 4
   M = pow(p, 2) - 1
   for x in range (1, 100000):
     s = (((s * N ) - 2 )) % M
     xx = [math.gcd(s, N)] + [math.gcd(s*p+x,N) for x in range(7)] + [math.gcd(s*p-x,N) for x in range(1,7)] 
     try:
        prime = min(list(filter(lambda x: x not in set([1]),xx)))
     except:
        prime = 1
     if prime == 1:
        continue
     else:
        break
   #print (s, x, prime, xx)
   return prime


In [70]: PrimeFinderLucasLehmer4(1009732533765211)                                                                                                                                        
Out[70]: 11344301

And from https://stackoverflow.com/questions/4078902/cracking-short-rsa-keys

In [71]: PrimeFinderLucasLehmer4(10142789312725007)                                                                                                                                       
Out[71]: 100711423

Test for the Primality of Mersenne numbers

1 Answers1