Forty megabytes of simplicity

Without further ado – six years after the previous one, the 52nd known Mersenne prime number has been found!

For those who don't closely monitor the approaching global warming for their own amusement by the scoundrels also known as the “community” GIMPS“(Great Internet Mersenne Prime Search), let me remind you, Mersenne numbers are twos raised to a power, minus one.

It has been proven that such numbers are sometimes, very rarely, prime – and in this case the exponent (that same power of two) is certainly also a prime number. Until the middle of the last century, the search for such numbers was rather sluggishbut with the advent of computers, of course, it rushed forward – first of all, of course, thanks to the presence algorithm search with polynomial complexity.

Since then, Mersenne prime numbers (MPNs) have held almost the entire podium of honor for the largest known prime numbers.

So that you understand what sizes we are talking about. Modern cryptography operates with prime or pseudo-prime numbers hundreds and thousands of bits long, but the current frontier of work on finding Mersenne prime numbers is located in the vicinity of this:

$2^{125000000} - 1$

Each candidate for simplicity in the vicinity of exponent 125 million, this is a number with a length of more than 40,000,000 (forty million) decimal digits, which requires about a day of operation on a powerful video card or several days on a “regular” server CPU to verify.

I rushed to please the habro audience faster than any official press release, which is why the latest PFM is not on this graph.

Verifying the first Mersenne prime discovered by the GIMPS project, M(1,398,269), took 0.05 gigahertz-days (an internal GIMPS unit, approximately equal to the work of one 1GHz Pentium 4 core per day). This was in 1996. The last found PFM, M(136 279 841) “weighs” already 759 GHz*days. You can look at the first numbers or download the archive with the full version right here.

It turns out that over 28 years, the complexity of calculations has grown by four orders of magnitude, significantly surpassing Moore’s law.

However, GIMPS not only does not lose heart, but on the contrary, it is increasing its momentum. Over the past 10 years, in addition to the natural emergence of increasingly powerful CPUs and GPUs, qualitative leaps have been made. Through the joint efforts of mathematicians and programmers, with the moral support of ordinary project participants like me, new algorithms have been implemented:

Probabilistic Miller-Rabin testalso known as PRP.
Error correction method Robert Herbix, who reduced the probability of a hardware error in calculations to almost zero.
Using VDF, “Verifiable Delay Function“, thanks to which it became possible to abandon the “heavy” verification tests and, in fact, double the overall productivity of the project.

Six years of waiting have been rewarded again (since this is already the third PFM that I have seen since joining the project), you can exhale, blow off the dust from the fans… and rush further along this endless (not proven!) road to the next huge and practically useless in everyday life number.