20210921, 05:51  #1 
Sep 2021
1 Posts 
How long does it take to test next mersenne number
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?

20210921, 08:20  #2 
Einyen
Dec 2003
Denmark
110100010100_{2} Posts 
Testing for primality and factorizing are 2 different tasks. The primality test for Mersenne Numbers is called the LucasLehmer 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. Last fiddled with by ATH on 20210921 at 08:53 
20210921, 12:04  #3 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
2^{2}·1,669 Posts 
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 P1 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.
Last fiddled with by kriesel on 20210921 at 12:10 
20210921, 12:38  #4 
Feb 2017
Nowhere
3·13·151 Posts 
(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_{1277}, or 2^{1277}  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 RSA2048 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 RSA2048, 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 primeproving 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. 
20210921, 14:22  #5  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
15024_{8} Posts 
The usual GIMPS process currently is "enough" TF, "adequate bounds" P1 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 P1, and eventually ECM and P+1 factoring.
(Cue LaurV with TF to all but the last bit level, P1, 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 Quote:
Last fiddled with by kriesel on 20210921 at 15:37 

20210921, 15:08  #6 
Aug 2002
Buenos Aires, Argentina
5AE_{16} Posts 
Furthermore, completely factor a Mersenne number (if it cannot be done with trial factoring, P1 or ECM) requires SNFS which runs a lot faster than GNFS. So factoring a nbit Mersenne number is far easier than a nbit RSA candidate.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How long should I run Prime95 torture test?  eliteassassin  Software  2  20190522 06:34 
How long it takes to factoring the 512bit number?  Pepek  Msieve  5  20120914 16:32 
how long it will take factoring a big number 512b  sinide  Factoring  8  20101119 08:03 
How long before you found your first composite number?  Bundu  Data  3  20040814 12:21 
Self Test going on way too long HELP HELP HELP  Jwb52z  Software  9  20030114 01:45 