mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2021-09-21, 05:51   #1
polad
 
Sep 2021

110 Posts
Default 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?
polad is offline   Reply With Quote
Old 2021-09-21, 08:20   #2
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

52×127 Posts
Default

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.

Last fiddled with by ATH on 2021-09-21 at 08:53
ATH is offline   Reply With Quote
Old 2021-09-21, 12:04   #3
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

5·13·89 Posts
Default

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, p2.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.

Last fiddled with by kriesel on 2021-09-21 at 12:10
kriesel is online now   Reply With Quote
Old 2021-09-21, 12:38   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

4,987 Posts
Default

(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 M1277, or 21277 - 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" Mp are first subjected to trial factoring. Various methods are used to look for "small" factors. If a factor q is found, Mp is thereby proven to be composite, and the cofactor Mp/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 Mp 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 Mp tests as a "probable prime," and the result verified, beer and champagne will be put on ice, and LL tests of Mp will be run on as many machines as can be mustered.
Dr Sardonicus is offline   Reply With Quote
Old 2021-09-21, 14:22   #5
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

10110100110012 Posts
Default

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

Quote:
Originally Posted by Dr Sardonicus View Post
If Mp tests as a "probable prime," and the result verified, beer and champagne will be put on ice, and LL tests of Mp 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.

Last fiddled with by kriesel on 2021-09-21 at 15:37
kriesel is online now   Reply With Quote
Old 2021-09-21, 15:08   #6
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

1,381 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
At present, the smallest Mersenne number which is known to be composite, but for which no factors are known, is M1277, or 21277 - 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.
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How long should I run Prime95 torture test? eliteassassin Software 2 2019-05-22 06:34
How long it takes to factoring the 512-bit number? Pepek Msieve 5 2012-09-14 16:32
how long it will take factoring a big number 512b sinide Factoring 8 2010-11-19 08:03
How long before you found your first composite number? Bundu Data 3 2004-08-14 12:21
Self Test going on way too long HELP HELP HELP Jwb52z Software 9 2003-01-14 01:45

All times are UTC. The time now is 22:03.


Thu Oct 21 22:03:54 UTC 2021 up 90 days, 16:32, 1 user, load averages: 1.96, 2.30, 2.37

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.