Mersenne Primes processing

I took interest in Mersenne Primes https://www.mersenne.org/. Great Internet Mersenne Prime Search (GIMPS) is doing the research in this field. These are Prime Numbers but are very large and few. 49th Mersenne Prime is 22 million digits long. It is unbelievable that one number can be 22 million digits.

I tried and could catch up to 8th Mersenne Prime which is 10 digits long and within 2 billions. I am using Postgres BIGINT which supports up to 19 digit long integers which 9 million billions. So, if I am processing 1 billion rows at a time, it would take me 9 million iterations. I can further use NUMERIC data type which supports 131072 digits to left of decimal and a precision 16383 digits. Of course I need to work with integers only. I do not need precision. Another alternative is Postgres’s CHAR VARYING which stores up to a billion. But it can not be used for calculations.

What Postgres provides is enough for any practical needs. My question is how the guys at GIMPS are calculating such large numbers. Are they storing these numbers in any database. Which database supports such large numbers. Am I out of sync with progresses made in database world.

I know they have huge processing power Curtis Cooper has mentioned 700 servers are being used to discover and verify the numbers. Exactly how much storage it is needed. What language is being used.

Just curiosity. Does this sound like I am out of job.

thanks

bb23850

Answer

Mersenne numbers are very easy to calculate. They are always one less than a power of 2:

select n, cast(power(cast(2 as numeric), n) - 1 as numeric(1000,0))
from generate_series(1, 100, 1) gs(n)
order by n;

The challenge is determining whether or not the resulting number is a prime. Mersenne knew that n needs to be prime for the number corresponding Mersenne number to be prime.

As fast a computers are, once the number has more than a dozen or two dozen or so digits, an exhaustive search of all factors is not feasible. You can see from the above code that an exhaustive search becomes infeasible long before the 100th Mersenne number.

In order to determine if such a number is prime, a lot of mathematics is used — some of it invented for or inspired by this particular problem. I’m pretty sure that it would be quite hard to implement any of those primality tests in a relational database.