Billion digit prime?

[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 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.

[ET_]

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.

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).

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

[lfm]

"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.

[Mini-Geek]

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).

[joblack]

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).

[ET_]

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

[joblack]

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