How long does it take to test next mersenne number

[polad]

I'm new to the community I'm sorry if this is not a correct place for this, but, I wonder how long does it take to test for Mersenne number? the reason I ask is that from a security standpoint, recommended RSA encryption is 2048 bit long, which is derived from 2 big prime numbers, it must be relatively easy to factorize 2^2048 rather than testing the next Mersenne number (current Mersenne number is m113903941). again the reason I ask is that supposing there are monetary incentives to find the next prime numbers, there is even more behind factorizing RSA keys, like for example there are keys that contains a lot of cryptocurrencies in it which worth billions of dollars. so how much wrong or right I am thinking about this?

[ATH]

Testing for primality and factorizing are 2 different tasks. The primality test for Mersenne Numbers is called the Lucas-Lehmer test and it can test for primality without searching for any factors, see section 4 here:
https://primes.utm.edu/mersenne/

It takes MUCH less computation to test M113903941 than it does to factorize a 2048 bit RSA number. The record for factoring general numbers without any special form with GNFS is only 829 bits:
https://en.wikipedia.org/wiki/Intege...zation_records

2048 bit number will be millions of times harder than an 829 bit number:
https://en.wikipedia.org/wiki/Genera...er_field_sieve

Using that heuristical complexity formula for GNFS, I got 233 billion times harder for 2048 bits than 829 bits, but I might have made a mistake. On top of that factoring an 829 bit number is already hundreds (probably thousands) of times more computation than testing M113903941.

[kriesel]

Welcome polad to the forum. For GIMPS reference info including run time scaling for the various computation types, there is a large compilation here. Rough rule of thumb is for same hardware and software, p^2.1 per test for the traditional LL or the much more reliable & efficient PRP/GEC/proof. Optimal P-1 or TF take around 1/40 of the primality test. For current first test wavefront assignments ~106M p, a RadeonVII GPU with fastest Gpuowl version takes ~1 day without reducing power for economy.

[Dr Sardonicus]

(More details may be found in various threads on this Forum, and at the GIMPS home page.)

At present, the smallest Mersenne number which is known to be composite, but for which no factors are known, is M₁₂₇₇, or 2¹²⁷⁷ - 1, which is a lot smaller than any RSA 2048. It's a 385 decimal digit composite number.

It is (usually) much, much easier to prove a composite number to be composite, than it is to find its factors. An RSA-2048 will almost certainly be proven to be composite using a PRP test, but that result will not give you the factors. And, if you have already accepted that the number is an RSA-2048, then you already know it is the product of two distinct primes, which is more than any PRP test can ever tell you.

If my understanding is correct, "new" M_p are first subjected to trial factoring. Various methods are used to look for "small" factors. If a factor q is found, M_p is thereby proven to be composite, and the cofactor M_p/q may be subjected to a PRP test. This usually proves the cofactor is composite. In that case, additional factors may be be sought, and sometimes found; the remaining cofactor is then subjected to a PRP test. If at some point the PRP test on a remaining cofactor does not show it to be composite (that is, the remaining cofactor is a "probable prime"), wild celebrations ensue. If the PRP "probable prime" cofactor is "small enough," the heavy prime-proving artillery can be trained on it, and the issue resolved. AFAIK there are no "probable prime" cofactors that have ever turned out to be composite, but (again, AFAIK) one could show up at any time, though I wouldn't bet on it happening any time soon.

If "enough" trial factoring fails to disclose any factors, these days M_p is next subjected to a PRP test rather than a determinative LL test. The reason for this is that a PRP test can now be verified relatively cheaply, whereas (again, if my understanding is correct) the only way to verify an LL test is to do it all over from scratch. If M_p tests as a "probable prime," and the result verified, beer and champagne will be put on ice, and LL tests of M_p will be run on as many machines as can be mustered.

[kriesel]

The usual GIMPS process currently is "enough" TF, "adequate bounds" P-1 once, PRP/GEC/proof, only LL upon PRP indication, with a halt immediately by the Mp hunters if a factor is found. Factor hunters follow along years later with deeper TF, bigger bounds P-1, and eventually ECM and P+1 factoring.
(Cue LaurV with TF to all but the last bit level, P-1, then TF the last bit level. But that is not how the assignments and work typically proceed automatically, via PrimeNet API or manual assignment.)
The process from addition of an exponent to a database to conclusion is described in #35 of https://www.mersenneforum.org/showpo...65&postcount=3

Originally Posted by Dr Sardonicus

If M_p tests as a "probable prime," and the result verified, beer and champagne will be put on ice, and LL tests of M_p will be run on as many machines as can be mustered.

In the rare case of a prime indication, how to proceed (first, check for possible error, contact the right people, otherwise maintain secrecy during verification and until publication of the GIMPS press release); if obvious error is ruled out, and a short rerun of the last checkpoint file reproduces the result, verification will be done before disclosure to GIMPS or the public, by a few runs in parallel, by a select group determined probably by Prime95 (George), on fastest available hardware for multiple separate software and hardware types. Past discovery verification examples here illustrate that process. Gpuowl V6.11-380 for LL with Jacobi check, on Radeon VII or similarly fast GPU, CUDALucas 2.06 on a fast Tesla GPU with frequent interim res64 comparisons to other runs, Mlucas LL with frequent interim res64 comparisons to other runs, and mprime LL with Jacobi check on dual-many-core Xeon workstations with ECC ram are likely. Xeon Phi Knights Landing based systems (64-72 cores in a single CPU and 16GB MCDRAM package) might also be fast enough and run mprime / prime95 or Mlucas for verification.

[alpertron]

Originally Posted by Dr Sardonicus

At present, the smallest Mersenne number which is known to be composite, but for which no factors are known, is M₁₂₇₇, or 2¹²⁷⁷ - 1, which is a lot smaller than any RSA 2048. It's a 385 decimal digit composite number.

Furthermore, completely factor a Mersenne number (if it cannot be done with trial factoring, P-1 or ECM) requires SNFS which runs a lot faster than GNFS. So factoring a n-bit Mersenne number is far easier than a n-bit RSA candidate.