CODEWITHSUNDEEP
algorithmmathprimescalculation
YesPleaseAllah
YesPleaseAllah

Reputation: 61

How do researchers manage to find such large primes?

This piqued my interest as I was trying to find a larger prime number, but I soon realised that the interpreter of my programming language soon popped an error when trying to insert a number with 24 million digits (2^82,589,933 − 1)to a variable. So I wondered, how do researchers manage to do this? How do they go through the process of finding numbers this large when there are clear computational limitations?

Upvotes: 2

Views: 161

Answers (1)

oppressionslayer
oppressionslayer

Reputation: 7224

A pow test of 65537 get's you the Mersenne numbers up to it's length at least, i'm not sure what test they use as i'm only able to climb up to 2**4423-1 after a couple of minutes:

for x in range(2,100000): 
   if pow(65537,2**x-2, 2**x-1) == 1: 
       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
2**3217-1 is prime
2**4253-1 is prime
2**4423-1 is prime

Based on President James K. Polk's comment i wrote the Lucas-Lehmer Primality test


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


# 20th Mersenne Prime
In [401]: LucasLehmer(4423)                                                                                                                                                                                 
Out[401]: True

# 21st Mersenne Prime
In [402]: LucasLehmer(9689)                                                                                                                                                                                 
Out[402]: True

# Some non random test:
In [404]: LucasLehmer(2727)                                                                                                                                                                                 
Out[404]: False

# 24th Merseene Prime
In [409]: LucasLehmer(19937)                                                                                                                                                                                
Out[409]: True

I played around with the math in the LL test and came up with a nice prime finder. Slow, not groundbreaking, but not bad:

from sympy import isprime

def PrimeFinderLucasLehmer(N):
   p = 1<<N.bit_length()-1
   if p == 2:
     return True
   s = 4
   M = pow(p, 2) - 1
   for x in range (1, (p-2)+1):
     s = (((s * N) - 2  )) % M
     mgcd = math.gcd(s, N)
     if  mgcd != 1:
        print(s, mgcd)
        if isprime(mgcd) == True:
           break
        else: continue
   return mgcd

From Cracking short RSA keys I was able to get the primes for those numbers rather quickly:

In [149]: PrimeFinderLucasLehmer(8114231289041741)                                                                                                             
15823901318551394674372071332152 1839221
Out[149]: 1839221

In [148]: PrimeFinderLucasLehmer(10142789312725007)                                                                                                            
36241961070961173943814389655700 100711423
Out[148]: 100711423

In [151]: PrimeFinderLucasLehmer(1009732533765203)                                                                                                             
157641275043535187903371634694 1823

Anyways, i thought that was interesting, so wanted to share. That was just with a tweak of the math.

Upvotes: 2

Related Questions