mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operation Billion Digits

Reply
 
Thread Tools
Old 2004-03-17, 14:42   #12
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2×3×293 Posts
Default

So the LL test does not win the "race to infinity" for finding ever larger primes (compared to other methods)?
jinydu is offline   Reply With Quote
Old 2004-03-17, 16:05   #13
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2·3,371 Posts
Default

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.
Prime95 is offline   Reply With Quote
Old 2004-03-17, 22:12   #14
biwema
 
biwema's Avatar
 
Mar 2004

38110 Posts
Default

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.
biwema is offline   Reply With Quote
Old 2004-03-18, 17:59   #15
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts
Default

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)?
(another reply)

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.
cheesehead is offline   Reply With Quote
Old 2004-03-20, 11:35   #16
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2·3·293 Posts
Default

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?
jinydu is offline   Reply With Quote
Old 2004-03-20, 18:11   #17
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

2×32×131 Posts
Default

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
wblipp is offline   Reply With Quote
Old 2004-03-20, 22:33   #18
clowns789
 
clowns789's Avatar
 
Jun 2003
The Computer

22·5·19 Posts
Default

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!
clowns789 is offline   Reply With Quote
Old 2004-03-21, 00:40   #19
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

2×32×131 Posts
Default

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
wblipp is offline   Reply With Quote
Old 2004-03-21, 19:30   #20
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

4,751 Posts
Default

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
ET_ is offline   Reply With Quote
Old 2004-03-21, 21:22   #21
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

44668 Posts
Default

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.
wblipp is offline   Reply With Quote
Old 2004-03-22, 00:06   #22
clowns789
 
clowns789's Avatar
 
Jun 2003
The Computer

22·5·19 Posts
Default

Can you modify Prime95 source code? Perhaps it could be 23.9.
clowns789 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
The "one billion minus 999,994,000" digits prime number a1call Miscellaneous Math 179 2015-11-12 14:59
Ten Billion Digits Mersenne Numbers aketilander Operation Billion Digits 13 2013-02-03 21:15
Operation Megabit Twin Oddball Twin Prime Search 370 2013-01-03 21:26
modulo operation for polynomials? smslca Math 3 2011-04-18 17:18
question range 1 billion to 2 billion? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.