mersenneforum.org Billion digit prime?
 Register FAQ Search Today's Posts Mark Forums Read

 2008-09-14, 19:15 #1 lfm     Jul 2006 Calgary 42510 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 Rabin-Miller 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 2008-09-14 at 19:29
2008-09-14, 19:25   #2
ET_
Banned

"Luigi"
Aug 2002
Team Italia

29×167 Posts

Quote:
 Originally Posted by lfm 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 relativly easy to figure out if the big one is prime. Ok. it is a long shot and maybe not worth even thinking about. First to get a billion digit prime this way we should start with billion plus 100 digit mersenne numbers so that the large factor would still be a billion digits long.
Checking primality of such number by trial-division would take forever, even a Lucas-Lehmer 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 2008-09-14 at 19:27

 2008-09-14, 19:44 #3 lfm     Jul 2006 Calgary 52×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 2008-09-14 at 20:03
 2008-09-14, 20:30 #4 Mini-Geek 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 Mini-Geek on 2008-09-14 at 20:31
2009-01-05, 14:37   #5
joblack

Oct 2008
n00bville

2×5×73 Posts

Quote:
 Originally Posted by ET_ Don't even think about it Checking primality of such number by trial-division would take forever, even a Lucas-Lehmer test would take more than 850 years (without finding factors).
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).

2009-01-05, 14:50   #6
ET_
Banned

"Luigi"
Aug 2002
Team Italia

29·167 Posts

Quote:
 Originally Posted by joblack 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).
850 years of Pentium 4, maybe the site is outdated

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^560000000-1), 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

2009-01-07, 01:17   #7
joblack

Oct 2008
n00bville

2×5×73 Posts

Quote:
 Originally Posted by ET_ 850 years of Pentium 4, maybe the site is outdated 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^560000000-1), because this way a billion digit number would be six time in size. Luigi
Damned you´re absolutely right ...

 Similar Threads Thread Thread Starter Forum Replies Last Post CRGreathouse Number Theory Discussion Group 51 2018-12-16 21:55 a1call Miscellaneous Math 179 2015-11-12 14:59 Unregistered Information & Answers 7 2010-08-12 06:25 MESCALINE1968 Lone Mersenne Hunters 2 2005-06-06 22:06 TTn 15k Search 15 2004-10-18 03:11

All times are UTC. The time now is 15:08.

Wed Aug 10 15:08:42 UTC 2022 up 34 days, 9:56, 4 users, load averages: 2.08, 1.94, 1.66