20080914, 19:15  #1 
Jul 2006
Calgary
425_{10} Posts 
Billion digit prime?
Actually factoring might find a billion digit prime! It is highly improbable but if a mersenne number has just two factors and we find the small one, its relatively easy to figure out if the big one is prime.
Well by relatively easy, perhaps I am mistaken. Even a RabinMiller probable prime test is slower than a LL test for mersennes. Not sure how much slower it is tho. Ok. it is a long shot and maybe not worth even thinking about. First to get a billion digit prime this way we would need to start with billion plus 100 digit mersenne numbers so that the large factor would still be a billion digits long. Last fiddled with by lfm on 20080914 at 19:29 
20080914, 19:25  #2  
Banned
"Luigi"
Aug 2002
Team Italia
29×167 Posts 
Quote:
Checking primality of such number by trialdivision would take forever, even a LucasLehmer test would take more than 850 years (without finding factors). And primality checking of a number with no particular notation (as would be the bigger factor) is actually limited to 15.000 digits by actual software (multicore Primo), while we had at least a 500.000.000 digits number. Luigi Last fiddled with by ET_ on 20080914 at 19:27 

20080914, 19:44  #3 
Jul 2006
Calgary
5^{2}×17 Posts 
"multicore primo" I can't find what this is. Could you tell me more about it? Or where to find more about it?
Its ok, I found it. It seems it no longer holds the record. See: http://www.ellipsa.net/public/primo/...Multiprocessor the "distributed ecpp" has a 20k digit prime proved. Still no help to us of course. Another consideration is the odds that the two factors would be so lop sided. The vast majority of two factor composites will have two large factors. It would be like the odds of finding a 77 digit or smaller number out of random 500 million digit numbers. Last fiddled with by lfm on 20080914 at 20:03 
20080914, 20:30  #4 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
2·3·23·31 Posts 
Regardless of the exact method used on numbers of no specific form (e.g. the larger of the two in what you're referring to), factoring LL numbers (with an efficient algorithm) is faster. Fully factoring an LL number with the algorithm in Prime95, for instance, with >1B digits would take an impossibly long amount of time (as in, an enormous supercomputer that pushes the limits of theoretical possible speed would take billions of years to factor it).
Last fiddled with by MiniGeek on 20080914 at 20:31 
20090105, 14:37  #5 
Oct 2008
n00bville
2×5×73 Posts 
Could you elaborate the 850 years? With a Quad Q6600 (4 x 3 GhZ) a 560M number would need estimated 11 years (checked with Prime95).

20090105, 14:50  #6  
Banned
"Luigi"
Aug 2002
Team Italia
29·167 Posts 
Quote:
Anyway billion digits numbers start at about 3321928097, twice a 560 Million digits number. I hope that you did not take 560M as the exponent (i.e. 2^5600000001), because this way a billion digit number would be six time in size. Add that doubling the exponent would require about 4*time to finish, and you're done: 11 years * 3.2 (4 threaded CPU ecfficiency) * 6 (= 3.3G/560M) * 4 (time factor), you get 844.8 years... Luigi 

20090107, 01:17  #7  
Oct 2008
n00bville
2×5×73 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Is CEMPLLA 1.5 "the only software in the world capable of discovering" something? Not really.  CRGreathouse  Number Theory Discussion Group  51  20181216 21:55 
The "one billion minus 999,994,000" digits prime number  a1call  Miscellaneous Math  179  20151112 14:59 
question range 1 billion to 2 billion?  Unregistered  Information & Answers  7  20100812 06:25 
Lucas test for billion bit prime  MESCALINE1968  Lone Mersenne Hunters  2  20050606 22:06 
10 digit prime in e  TTn  15k Search  15  20041018 03:11 