mersenneforum.org Operation: Billion Digits
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2004-03-17, 14:42 #12 jinydu     Dec 2003 Hopefully Near M48 2×3×293 Posts So the LL test does not win the "race to infinity" for finding ever larger primes (compared to other methods)?
2004-03-17, 16:05   #13
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

2·3,371 Posts

Quote:
 Originally Posted by jinydu So the LL test does not win the "race to infinity" for finding ever larger primes (compared to other methods)?
LL, proth, generalized fermat are all O(n^2 log n). The LL test has the smallest constant. Let's say that the LL test is 1.5 times as fast as the generalized fermat, and 4 times faster than the proth test. Your best algorithm to find a billion digit prime is then:

1) search for a 1 to 1.5 billion digit Mersenne prime. If none found:
2) start searching for billion digit generalized fermats too.
3) If you get to 4 billion digit Mersenne numbers and 2.6 billion digit generalized fermat numbers and still haven't found a prime, then start searching for billion digit Proth primes too.

 2004-03-17, 22:12 #14 biwema     Mar 2004 38110 Posts So if there are no Mersenne Primes with less than 1.5 billiion digits, it is the best thing to search for generalized fermat primes, becasue there are pleny of them. you can just square the basis and half the exponent, and the searching field gets much bigger. If we estimate about 1000 cpu years on a average P4 for a single test, and a chance of 1 in 300Million I doubt that it is worth the electricity just for the price. But the fascination in that is somewhere else.
2004-03-18, 17:59   #15

"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts

Quote:
 Originally Posted by jinydu So the LL test does not win the "race to infinity" for finding ever larger primes (compared to other methods)?

No, the L-L test always wins, compared to other methods, for same-sized numbers.

But there are only three or four Mersenne numbers (not to mention that most have composite exponents) in any given range denoted by a certain number of decimal digits, whereas there are millions and millions of exactly-1,000,000,000-digit non-Mersenne primes waiting to be discovered by methods other than L-L.

Then, as one extends L-L testing to Mersenne numbers of more than 1,000,000,000 digits, the time required gets longer, and eventually exceeds the time required for a non-L-L test of a 1,000,000,000-digit non-Mersenne number. After one factors in the differing predicted densities of primes, one finds a tradeoff point at which it's more cost-effective to switch to an asymptotically slower method on smaller numbers.

 2004-03-20, 11:35 #16 jinydu     Dec 2003 Hopefully Near M48 2·3·293 Posts So if I ask for a prime with at least n digits in as small a time as possible, which method should I use as n approaches infinity?
2004-03-20, 18:11   #17
wblipp

"William"
May 2003
New Haven

2×32×131 Posts

Quote:
 Originally Posted by ET_ 3,321,928,171 no factor up to 60.033 bits, k=179,309,108 Luigi
Will you be taking this any further? Did you use your own program?

William

2004-03-20, 22:33   #18
clowns789

Jun 2003
The Computer

22·5·19 Posts

Quote:
 Originally Posted by wblipp Will you be taking this any further? Did you use your own program? William
How about we have one person Advanced P-1 it while another Advanced ECM 100 curves? If that doesn't work, someone could factor about 118 bits. We'll figure it out after that.

LLs would take 852 years, 209 days, 1 hours, 27 minutes for that exponent!

2004-03-21, 00:40   #19
wblipp

"William"
May 2003
New Haven

2×32×131 Posts

Quote:
 Originally Posted by clowns789 How about we have one person Advanced P-1 it while another Advanced ECM 100 curves? If that doesn't work, someone could factor about 118 bits.
Can we really do anything except trial factor? P-1, P+1, and ECM all perform calculations modulo the billion digit number - I thought that would be a problem. Trial factoring requires calculations modulo the trial factor - a much smaller number.

Will Prime95 AdvancedFactor work this large? It didn't work my machine. I think Luigi was using his own program. I was using Excel with the Zmath addin.

William

2004-03-21, 19:30   #20
ET_
Banned

"Luigi"
Aug 2002
Team Italia

4,751 Posts

Quote:
 Originally Posted by wblipp Will you be taking this any further? Did you use your own program? William
I used my program. If you think it could be useful, I will go further, just tell me the bit-depth you need (just remember my program is far slower than Prime95...)

Luigi

2004-03-21, 21:22   #21
wblipp

"William"
May 2003
New Haven

44668 Posts

Quote:
 Originally Posted by ET_ I used my program. If you think it could be useful, I will go further,
Useful? That's a pretty strong standard. Operation Billion Digits is a Children's Crusade, needing fifteen-twenty years of continuing Moore's Law before the LL test becomes feasible. I thought it would be fun to continue a while further, though. And the only paths I see to advance Project Billion Digits are to advance the trial factoring of this candidate or to trial factor some other candidates.

Quote:
 Originally Posted by ET_ just remember my program is far slower than Prime95
What methods are you using to filter the k values before determining 2kp+1? We only need to test prime values of 2kp+1, so various sieving methods are possible. In my Excel spreadsheet I used a wheel of size 13# to automatically avoid k values where 2kp+1 had any divisors 13 or less, but larger wheels and/or other methods could make sense in a C program.

In the spreadsheet, I noticed that occasionally the value of mod(2^p, 2kp+1) was a power of 2, and this leads to other Mersenne factors. You might want to consider checking for these possibilities and saving the results for later processing.

 2004-03-22, 00:06 #22 clowns789     Jun 2003 The Computer 22·5·19 Posts Can you modify Prime95 source code? Perhaps it could be 23.9.

 Similar Threads Thread Thread Starter Forum Replies Last Post a1call Miscellaneous Math 179 2015-11-12 14:59 aketilander Operation Billion Digits 13 2013-02-03 21:15 Oddball Twin Prime Search 370 2013-01-03 21:26 smslca Math 3 2011-04-18 17:18 Unregistered Information & Answers 7 2010-08-12 06:25

All times are UTC. The time now is 04:07.

Wed Apr 1 04:07:47 UTC 2020 up 7 days, 1:40, 0 users, load averages: 2.28, 2.20, 1.97