Delivered-To: luke@ndatech.com X-Sender: rugeley@pop3.demon.co.uk X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Sat, 15 Dec 2001 22:44:57 +0000 To: Luke Welsh From: mersenne-digest-invalid-reply-address@base.com (Mersenne Digest) (by way of Gordon Spence ) Subject: Mersenne Digest V1 #914 Mersenne Digest Wednesday, December 5 2001 Volume 01 : Number 914 ---------------------------------------------------------------------- Date: Tue, 4 Dec 2001 18:11:33 -0000 From: bjb@bbhvig.uklinux.net Subject: RE: Mersenne: Re: Factoring benefit/cost ratio On 4 Dec 2001, at 1:19, Paul Leyland wrote: > > > From: bjb@bbhvig.uklinux.net [mailto:bjb@bbhvig.uklinux.net] > > > > > > (Aside - we're rather more likely to find a 75-bit factor than a 75- > > digit factor. In fact, finding a 75-digit prime factor of a > > "no factors > > known" Mersenne number with an exponent under 80 million would > > be a significant achievement in itself. > > Finding a 75-digit prime and non-algebraic factor of any integer with > more than, say, 200 digits would be a significant achievement. The > record today is 55 digits; it reached 53 digits 3 years ago and only a > handful of factors with 50 or more digits have been found ever. I have > precisely one of them to my credit 8-) Sure. Not quite the same since there appears to be no certificate of primality, but on 30 Aug 2001 there was a message on this list to the effect that M727 (c219) = prp98.prp128. So much ECM work was done on M727 (before the NFS people started work) that it is highly unlikely that there are any factors < 10^50, which means that at least the 98-digit probable prime is almost certainly a genuine prime. (Maybe that's been proved by now. ECPP on general numbers of around 100 digits isn't very expensive.) I think the 55 digit record applies to ECM. A number of much larger factors (not counting cofactors) have been found using number field sieve techniques. > > > At the moment, having found one factor, we quit. That's sufficient > > effort for the purpose of trying to find Mersenne primes. A little > > more work might break the cofactor down further. > > Actually, some of us don't quit. But we're a small bunch of weirdos, > and we only work on tiny exponents anyway. I was speaking for the project rather than myself. I'm also one of the small bunch of weirdos. Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 4 Dec 2001 10:30:05 -0800 From: "Paul Leyland" Subject: RE: Mersenne: Re: Factoring benefit/cost ratio > Sure. Not quite the same since there appears to be no certificate of > primality, but on 30 Aug 2001 there was a message on this list to > the effect that M727 (c219) = prp98.prp128. So much ECM work > was done on M727 (before the NFS people started work) that it is > highly unlikely that there are any factors < 10^50, which means > that at least the 98-digit probable prime is almost certainly a > genuine prime. (Maybe that's been proved by now. ECPP on > general numbers of around 100 digits isn't very expensive.) Ah, but SNFS-able numbers only half-count because they are so easy ;-) You're correct: I was forgetting the Cunningham factorizations which yielded large penultimate primes. There are quite a few by now. All the factors have indeed been proved prime. > I think the 55 digit record applies to ECM. A number of much larger > factors (not counting cofactors) have been found using number field > sieve techniques. Correct. I do not know of any larger penultimate factors of hard integers with more than 200 digits. The largest I know of has 78 digits, but that is from RSA-155, which only has 155 digits. Paul _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 04 Dec 2001 13:55:44 EST From: EWMAYER@aol.com Subject: Re: Mersenne: Re: SF Bay area GIMPS party I'm still waiting to hear from a few people before I finalize the venue. The time is set: 6pm Friday for drinks and chit-chat, eat around 7. - -Ernst _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 04 Dec 2001 20:19:00 +0000 From: Gordon Spence Subject: Mersenne: Re: Mersenne Digest V1 #913 Brian Beesley wrote >Ah, but George's GIMPS stats encourage factoring by removing LL >testing credit when a factor is subsequently found. (Either you >should have done more factoring before you started LL testing, or >the factoring you did was expensive!) Okay then, I just turned this in 7213061 67 DF 168956092713627344887 04-Dec-01 13:18 labrat04 How do we confirm the original tester has now *lost* this credit? >Nathan Russell wrote >At 07:57 PM 12/2/2001 +0000, Gordon Spence wrote: > >A particularly sore point. If we maintained a top "savers" list whereby > >for every factor found you were credited with the time an LL test would > >have taken, then I and the other "Lone Mersenne Hunters" would pulverise > >these big university teams. > >Should George get credit for eliminating all those composite exponents when >he made his initial list in the mid-1990's? Yes of course he should! >He probably found over a dozen times as many composites in (at a guess) >under two minutes than we'll EVER find, at least until the project is >extended past 80M. The Lone Mersenne Hunters are searching right up to that limit, the only reason we don't go any higher is because the current version of Prime maxes out at 79.999M... Ernst Mayer wrote: >OK, the San Francisco Bay area GIMPS get-together will >take place this coming Friday, 7. December, in the south >bay area (precise venue to be decided soon - see below.) >Any GIMPS participant or Mersenne prime fan is welcome >to join us, along with anyone else you'd like to bring - >this is not a formal party.For those not coming from the San Jose area, >the venue >will be close to a Caltrain station, and hence should be >reachable from e.g. SFO airport or other outlying areas. >I'm also going to try to arrange what ridesharing I can, >so if you can provide a ride or need a ride, please let >me know. I looks like several folks from far-flung places >will be attending, so should be a quite interesting >company. Alas, Luke Welsh can't attend, but he suggested >several venues, two of which form my short list. > >1) Tied House, Mountain View >2) Faultline Brewery, Sunnyvale > >1) is very close to a Caltrain station; 2) supposedly >has very good food. I can vouch for the fact that the food is in fact excellent, and the creme caramel a speciality. Considering it's CA they make not a bad attempt at brewing beer either! Unfortunately my next visit to San Jose is not till the week before Xmas, so it's cold,wet and dark UK for me...but I'll have a virtual pint with you ;-) regards Gordon M2976221 is still the largest prime listed in Knuth by the way ;-) _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 04 Dec 2001 20:36:00 +0000 From: Gordon Spence Subject: Mersenne: Re: Mersenne Digest V1 #913 TorbenS wrote > No you wouldn't because they would like yourself go to do only >factoring work, Only factoring work? I found over 95% of those on a single P133...... Brian Beesley wrote >I've triple-checked thousands of small exponents - some of the >ones where the accepted residual was recorded to only 16 bits or >less, which makes the chance of an undetected error _much_ >greater (though still quite small) - so far no substantive errors in the >database have come to light. A very few (think fingers of one hand) >instances of incorrectly matched residuals have come to light - >completing the double-check in these cases proved that one of the >recorded residuals was correct. Currently my team report cleared list shows 338 double checks and 12 double checked factored including this monster 6630223 87 DF 195139088771490335223859559 07-Apr-01 07:58 trilog (In fact when it was checked in PrimeNet initially rejected it because it was longer than this sort of check was supposed to find! Has anyone found a factor bigger than 87 bits using Prime95?) Of course some of these may be because the original check went to a lower bit depth than the version of Prime95 that I used. I know from doing "deep factoring" in the 60m range that one more bit of factoring can find a "lot" of extra factors...So if we say that as a ballpark figure half of these are due to an increase in factoring depth, then the error rate from this admittedly small sample is 1.78% or in other words of the current 137,924 exponents less than 20m with only a single LL test we can expect to find just under 2500 exponents with an incorrect result. regards Gordon _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 04 Dec 2001 16:02:23 EST From: EWMAYER@aol.com Subject: Mersenne: Re: SF Bay area GIMPS party OK, since I only received a location preference from one person (thanks, Spike!), their vote gets counted: WHAT: 3rd not-quite-annual San Francisco Bay Area GIMPS Get-together WHO: Any GIMPS member (we'll take your word for it :) or prime number enthusiast. Bring a friend/spouse /significant other/not-so-significant other WHEN: Friday, 7. December. Drinks start at 6pm, dinner@7 WHERE: Tied House Cafe & Brewery 954 Villa Street Mountain View CA 650-965-2739 (see description below) * * * I was going to offer a large couch in my apartment to anyone who needs a place to stay overnight, but that's already been taken by one of the attendees who asked. If anyone else who plans to attend needs or can offer a place to stay the night, please let me know. Re. Rides: John Pierce has kindly offered rides in his new mega-mobile-SUV-kind-of-vehicle to folks from the Santa Cruz area. If you live (say) in Monterey or Pacific Grove, you'll probably want to meet him at some convenient location in SC. John says this thing even has captain's chairs, so if you want to sit in one of those, practice your 'Star Trek' phrases, you know, "Make it so," "Steady as she goes, Helm," "Scotty, I need warp now," and so forth. (I never did figure out the first name of that "Helm" fellow - Matt, perhaps? :) - - Peter Montgomery (assuming he can make it that evening) needs a ride from the North Bay, preferably from Marin County, but I believe he can also meet someone in San Francisco, if needed. - - If anyone else needs/can share a ride, let me know. * * * Here is the venue description from citysearch.com: Restaurant Review (I've added some very minor comments of my own, enclosed in [] - EWM.) Brews We Like The Cascade Amber is the most popular, and is quite good. The Alpine Gold ale is clean in both hop aroma and finish. Look for seasonal brews such as the strong IPA [Or the M#39 Pale Ale]. Bites We Like Stay away from anything that sounds complicated (citrus shrimp, apple gorgonzola salad, [generalized Fermat primes,] et cetera). Stick with pub grub like the burgers, sausage sampler plate and the huge black bean nachos. The Look Big beer halls with tall ceilings to accommodate the huge vats full of tasty brews [and future world-record-prime posters]. The San Jose location has a particularly attractive patio area. The Crowd Young professionals mingle with serious beer snobs in a sports-fan-[and-number-theory-]friendly environment. The Critics Agree The Tied House beers have received many awards for the brews, including 13 [a Mersenne prime exponent] Great American Beer Festival medals. [tip sheet] One of Silicon Valley's Best Nominated for best brewpub for its comfortable atmosphere and quality beers. Catch a Show Grab a brew before a show. The Mountain View location is near Shoreline Amphitheatre Another Good Brewpub Try the Los Gatos Brewing Company [maybe next time.] * * * I look forward to seeing my fellow GIMPSers there! - -Ernst _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 04 Dec 2001 22:28:56 +0100 From: Henk Stokhorst Subject: Mersenne: p-1 records Gordon Spence wrote: > > Currently my team report cleared list shows 338 double checks and 12 > double checked factored including this monster > > 6630223 87 DF 195139088771490335223859559 07-Apr-01 07:58 trilog > > (In fact when it was checked in PrimeNet initially rejected it because > it was longer than this sort of check was supposed to find! Has anyone > found a factor bigger than 87 bits using Prime95?) 10750127 103 F 7866348588447235992766781311399 14-Jan-01 10:57 Arnor Aries 11781977 103 F 8765843379800293878049454631169 15-Dec-00 20:06 mmesser Work_NT 11926087 103 F 8167296501437056056688534765783 07-Jan-01 10:52 rsuntag Kayak_XU 12348829 103 F 9722991869324431663702571958950 22-Feb-01 07:48 SCUM C7375CE26 12423109 103 F 9668741834447195893278167681393 01-Mar-01 14:36 CamLewis work-syn-1 12469069 103 F 7539700408276934619634505308431 09-Mar-01 14:17 chbarr2 Domain01 these are the first 6 I found. YotN, Henk _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 04 Dec 2001 16:52:37 -0500 From: Nathan Russell Subject: RE: Mersenne: Re: Factoring benefit/cost ratio At 06:11 PM 12/4/2001 +0000, bjb@bbhvig.uklinux.net wrote: >Sure. Not quite the same since there appears to be no certificate of >primality, but on 30 Aug 2001 there was a message on this list to >the effect that M727 (c219) = prp98.prp128. Does anyone know how much CPU time was spent? >So much ECM work >was done on M727 (before the NFS people started work) that it is >highly unlikely that there are any factors < 10^50, which means >that at least the 98-digit probable prime is almost certainly a >genuine prime. (Maybe that's been proved by now. ECPP on >general numbers of around 100 digits isn't very expensive.) Especially when one uses Primo, which makes numbers of even a thousand digits take perhaps an afternoon on my machine. I doubt very strongly I'm the first, but just for reference: http://www.mail-archive.com/mersenne@base.com/msg06304.html http://www.acsu.buffalo.edu/~nrussell/M727.zip Nathan _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 4 Dec 2001 21:59:38 -0000 From: bjb@bbhvig.uklinux.net Subject: Re: Mersenne: New exponents On 4 Dec 2001, at 11:48, Nathan Russell wrote: > For the information of the list, the folks who *want* to try to get > exponents below (the presumed) M#39 might want to look into manually > fetching work at 2:00 (IIRC) in the morning Eastern standard (7 or 8 GMT), > when the server releases exponents of folks who have stopped participating > without properly quitting. The best time to get small exponents is 0601 GMT. I thought the point of the original message was that someone specifically wanted to get larger exponents. The best time to do that is 0559 GMT. You do run a "risk" that someone will throw back a "small" exponent just before you grab one, but you can always throw it back & try again another day. You face a small risk that the original tester > will submit a result, but even in that case you'll get credit for the > double-check (though that would be a small consolation if a prime were > found). This would be an interesting situation: (a) I acquire an assignment, let it expire but carry on working on it (b) You grab the assignment when it's recycled Case 1: I finish first, find a prime and announce my discovery. I did the work but the exponent is assigned to you! Who gets the credit??? Well, I suppose I _could_ grab the credit by making a public announcement without checking the result in to GIMPS/PrimeNet, but this is definitely against the spirit of the project. Conversely you hardly deserve to get the credit for a discovery which you haven't yet made. I think it's better to withhold publicity until you finish, then we can be treated as co-discoverers. Case 2: We both finish independently (it doesn't matter in which order, provided that we are not in direct contact with each other & aren't aware of each other's discovery until after we have communicated the result to GIMPS/PrimeNet). This case is clear cut, we're co-discoverers. Case 3: You finish first & communicate your discovery through GIMPS/PrimeNet in the "usual" way. This case is also clear, you're the discoverer. This probably needs to be spelled out in legal language just in case it happens in a situation where a substantial cash prize is involved (enough for it to be worthwhile paying to fight a court case). Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 04 Dec 2001 17:40:29 -0500 From: Nathan Russell Subject: Re: Mersenne: p-1 records At 10:28 PM 12/4/2001 +0100, Henk Stokhorst wrote: (as part of a listing of factors found by himself) >12348829 103 F 9722991869324431663702571958950 22-Feb-01 07:48 >SCUM C7375CE26 Is this a bug in the reporting software? I don't have the tools to work it out exactly, but a 103-bit number should be slightly larger than 2^103, or 10141204801825835211973625643008. the factor 9722991869324431663702571958950 is one digit too short, and thus appears to be truncated. The fact that it is even, and there is a relative shortage of Mrsenne numbers wandering about with even factors (or, for that matter, factors of five) would seem to me to confirm that. However, if it were truncated it couldn't have the beginning digit 9 - then it'd have 106 bits, unless my mental math is off. Something really odd is going on. Nathan _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 04 Dec 2001 17:59:42 -0500 From: George Woltman Subject: Re: Mersenne: New exponents At 09:59 PM 12/4/2001 +0000, bjb@bbhvig.uklinux.net wrote: >This would be an interesting situation: > >(a) I acquire an assignment, let it expire but carry on working on it > >(b) You grab the assignment when it's recycled > >Case 1: I finish first, find a prime and announce my discovery. I did >the work but the exponent is assigned to you! Who gets the >credit??? You, get the credit. User b will be mighty disheartened. I know first hand. Slowinski's Cray beat my own Pentium-90 by just a few days in the discovery of M#34. As to legal issues, the disclaimer section of the download page states: We are not responsible for lost prize money, fame, credit, etc. should someone accidentally or maliciously test the number you are working on and find it to be prime. _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 4 Dec 2001 22:59:07 -0000 From: "Daran" Subject: Re: Mersenne: Re: Factoring benefit/cost ratio - ----- Original Message ----- From: To: "Daran" Cc: Sent: Monday, December 03, 2001 11:22 PM Subject: Re: Mersenne: Re: Factoring benefit/cost ratio > On 3 Dec 2001, at 20:45, Daran wrote: > > > Shouldn't that be 1.015 for double-checking assignments? > > I think 1.03... Yes, of course. > ...However you do have a point. P-1 limits do depend on > the trial factoring depth,... Now I'm puzzled. Obviously both P-1 and trial factoring limits both depend upon the exponant, so will correlate, but I don't see a direct dependency between them. > and are much smaller for DC assignments > than for first tests, so there is already something "built in". Right. I'd noticed that my P-1 probabilities for DC assignments were about half that for LLs, but I'd attributed that to the differences between the magnitudes of the exponants. This makes more sense. > > Also does the cost part of the calculation recognise the increased cost of > > trial-factorisation after 2^64? > > Yes. The trial factoring depth is constant at 64 bits from ~8.5 > million to ~13 million. Don't forget that the number of candidates > which need to be checked is _inversely_ proportional to the > exponent. Because any factor must be of form 2kp+1. [...] > > Finally if P-1 factorisation were to be spun off into a separate work unit, > > then the optimal arangement would be to trial factor while > > cost_of_trial_factoring * chance_of_P-1_factoring is less than > > cost_of_P-1_factoring * chance_of_trial_factoring. Then P-1 factorise. > > Then complete trial factorisation according to the above formula. > > Interesting - but I think the effect would be small. Perhaps, but the effort to implement (without spinning off P-1 into a separate work type) would also be small. The existing formula (cost_of_trial_factoring < chance_of_trial_factoring * cost_of_LL_test * 2.03) ignores the effect of P-1. A better formula would be:- cost_of_trial_factoring < chance_of_trial_factoring * (cost_of_P-1_factoring + (1-chance_of_P-1_factoring)*(cost_of_LL_test * 2.03). This change on its own would surely be trivial to implement. But then, if the P-1 fails, you might as well carry on and do a little more TF, which brings us back to the simpler formula I gave earlier. You might also want to lower your P-1 bounds a shade to take into account the fact that a successful factorisation may only save a little extra TF effort. The end result is a *tiny* reduction in the probability of finding a factor (because of the slight reduction in P-1 bounds). But you'll do less work, and if you do find one, you'll probably find it earlier. How much earlier? I've just completed P-1 on M656677 which took 8787 seconds which about 1.5% of the DC estimated to take 6 days 23 hours 43 minute equals 603780 seconds, compared with a 2.6% chance of success. My guess is that this would put it optimally just before the last round of TF, which is (or should be) close to the break-even point. I'd need an estimate for the time of the last round of TF to be any more precise. The calculation would also need to be repeated for a first-time LL assignment. My final remarks on the subject of early P-1 is the observation that TF and P-1 search overlapping factor spaces. Are there any gains to be had in TF from sieving out some of the smooth k's that an early P-1 failed to find? Could you structure the factor candidate generation code, so that unsieved list doesn't contain any smooth k's in the first place? Even if it's not possible or cost effective to do either of these, the fact that there are smooth k's among the candidates should lower the estimate for the probability of success. Another reason to spin off P-1 into a separate work type is to allow machines with heaps of memory to concentrate on this kind of work. A little experimentation shows that the probability of a successful P-1 with 400MB is roughly double that of one with a minimal configuration, and some machines will be doing LLs/DCs without the ability to P-1 at all. What I envisiage is that a virgin exponant would first go out to P-1(which would also do the first few rounds of TF, according to my earlier formula), then as a factoring assignment (to completion), then finally to LL and DC. > What about factoring to a "fractional" depth? With a roughly > logarithmic distribution of factors, surely about half the factors > between 2^n and 2^(n+1) would be smaller than 2^(n+0.5), whilst > searching to 2^(n+0.5) would take only about 41% of the time > taken to search the whole interval. This had occured to me. One could calculate the exact break-even point and TF thus far and no further. However the gains would be minimal for many exponants in the middle of the depth 'bands', which are already being near-optimally factored. Even those at the edges of the depth bands can't be very far from the break-even point. Also the server would need to record more information to enable TF to be taken a further at a later date. What about automating the eliptic curve factoring effort to make it more systematic? > Regards > Brian Beesley Daran G. _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 04 Dec 2001 19:36:54 EST From: EWMAYER@aol.com Subject: Mersenne: Re: SF Bay area GIMPS party p.s. p.s.: the reservation will be under the name "Mersenne." pps: I was hoping to be able to bill the whole thing to the good friar's expense account, but the abbot said "non" to that. Guess we'll have to pay for our own beer. :( _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 04 Dec 2001 20:22:36 -0500 From: George Woltman Subject: Re: Mersenne: p-1 records At 05:40 PM 12/4/2001 -0500, Nathan Russell wrote: >>12348829 103 F 9722991869324431663702571958950 22-Feb-01 07:48 > >Is this a bug in the reporting software? >Something really odd is going on. Yes. The structure used to pass back factors found only supports factors up to 32 digits. The server misreports the bit-length for very large factors. You may notice that when you finish an assignment two messages are sent to the server. One is the aforementioned C structure. The other is a text message (the same text as is written to results.txt). Fortunately, I use the text messages to update my databases which has no such 32 digit limitation. The largest factor found by P-1 factoring of large exponents is 35 digits: 13187813 63113922700063643342764849026462401 _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 5 Dec 2001 00:57:40 -0000 From: "Daran" Subject: Re: Mersenne: Re: Factoring benefit/cost ratio - ----- Original Message ----- From: "George Woltman" To: ; Sent: Tuesday, December 04, 2001 3:41 AM Subject: Re: Mersenne: Re: Factoring benefit/cost ratio > I think more of the discussion has centered around stats and the > formula for picking how far to trial factor, rather than whether factoring > is of some mathematical value... That's true, at least for my own recent contributions to this discussion. However, what I've been trying to do is float a few ideas for increasing the effectiveness of the factorising effort. If P-1 was done early, as I suggested, with bounds unchanged, then exactly the same Mersennes will get factored sooner, on average, and with less work. Ditto with the smooth k sieving idea. And if the cost of factoring is reduced, the optimal depth increases. The benefits of such an exercise are even greater if factors are given an intrinsic value of their own. Of course, the real scarce resource is not computer cycles, nor even ideas for improvement, but in programming effort to implement. Calculating that particular trade-off I leave to others. > -- George Daran G. _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 5 Dec 2001 01:18:39 -0000 From: "Daran" Subject: Re: Mersenne: New exponents - ----- Original Message ----- From: "Keith Garland" To: Sent: Monday, December 03, 2001 2:53 PM Subject: Mersenne: New exponents > Hi from Ireland - I have a few questions about how M39 will affect the > allocation of current/new exponents. Once the result has been announced I > suppose we will recommence searching above M39? No. We are looking for /all/ Mersenne primes, not just one larger than the biggest one we know. We don't know whether M#39 really is M39 or not, and the only way to find out is to test all smaller prime exponants. > I got a couple of new > exponents over the weekend - I assume that they are not necessarily > M39 in > order to maintain "secrecy". If so then, after the announcement, should we > dump our existing tests or finish off factoring things that are half > finished? Please finish them. > Does prime95 handle this scenario automatically - i.e. will new > exponents be automatically sent if a manual update is done? > > Thanks, > > Keith Daran G. _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 5 Dec 2001 00:57:53 -0000 From: "Daran" Subject: Re: Mersenne: Re: Factoring benefit/cost ratio - ----- Original Message ----- From: To: Sent: Tuesday, December 04, 2001 2:38 AM Subject: Re: Mersenne: Re: Factoring benefit/cost ratio > > and one that is decades (at least) behind GIMPS. The only reason we > > do any factoring at all is to reduce the time spent on LL testing. > > But if factoring is not really part of GIMPS's purpose (and I agree it > isn't), how can a separate factoring effort be "behind" GIMPS at all? > Aren't they measuring their progress in a different, non-comparable, > dimension? Say rather that there are various criteria by which the two projects can be compared. It's probably true that it would take them decades or more to completely factor a set of prime exponents comparable to those which GIMPS has verified composite. (and that's ignoring the effort to factorise the cofactors of Mersennes with composite exponents). They're probably not that far behind GIMPS in terms of total computing done. How far will depend upon how good they are at mobilising support. [...] > In reply to a statement of mine about "the extra benefit of finding a > specific factor", > Daran G. wrote: > >I can see no way of objectively quantifying this benefit. > > Well -- if there's no objective quantification of the extra benefit of > finding a specific factor, then it seems to me that there's no > objectively quantifiable justification for saying that it's not > valuable to do a certain amount of "extra" P-1 factoring on a > once-LL'd Mnumber. :) Can't argue with that. [...] > Daran G. wrote: > >It seems to be implicitely acknowledged in the way the trial > factoring > >depths are determined. > > But don't forget that this refers to a depth determined by Prime95 > _in the context of calculating the factoring tradeoff point for > maximizing GIMPS throughput for the "Test=" worktype_, NOT the context > of a "Factor=" or "Pminus1=" worktype where the user has explicitly > specified factoring limits, possibly for reasons beyond the ken of > Prime95. That seemed to be the question you were asking. [...] > I'm not saying that Prime95 should incorporate into its calculations a > nonzero value for the benefit of finding a specific factor. > > I'm saying that it is rational for someone to decide to factor past > the Prime95-calculated tradeoff points, and that it is unjustified to > criticize "extra" factoring on the grounds that going past the > Prime95-calculated tradeoff points is wasted effort. I agree. But you can look at this in terms of an even greater project than GIMPS - The Great Distributed Computing Project that encompasses all such efforts, and aims to use spare computing cycles to increase the knowledge base of humankind generally. What contribution one chooses to make depends upon ones own personal preferences. > Richard B. Woods Daran G. _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 5 Dec 2001 01:19:33 -0000 From: "Daran" Subject: Re: Mersenne: Re: Mersenne Digest V1 #912 - ----- Original Message ----- From: "Nathan Russell" To: Sent: Monday, December 03, 2001 8:29 AM Subject: Re: Mersenne: Re: Mersenne Digest V1 #912 > At 07:57 PM 12/2/2001 +0000, Gordon Spence wrote: > >A particularly sore point. If we maintained a top "savers" list whereby > >for every factor found you were credited with the time an LL test would > >have taken, then I and the other "Lone Mersenne Hunters" would pulverise > >these big university teams. > > Should George get credit for eliminating all those composite exponents when > he made his initial list in the mid-1990's? > > He probably found over a dozen times as many composites in (at a guess) > under two minutes than we'll EVER find, at least until the project is > extended past 80M. Don't forget all the integers that were eliminated because they weren't Mersenne numbers, the non-integral rationals, the uncountable infinity of non-rational real numbers, complex numbers, quaternians... The rest of our efforts have been trivial in comparison. :-) > Nathan Daran G. _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 05 Dec 2001 09:35:01 +0100 From: Henk Stokhorst Subject: Re: Mersenne: p-1 records Nathan Russell wrote: >> 12348829 103 F 9722991869324431663702571958950 22-Feb-01 07:48 >> SCUM C7375CE26 > > > Is this a bug in the reporting software? I don't have the tools to > work it out exactly, but a 103-bit number should be slightly larger > than 2^103, or > 10141204801825835211973625643008. > the factor > 9722991869324431663702571958950 > is one digit too short, and thus appears to be truncated. 2^103 is the upper limit I believe, not the lower limit. YotN, Henk _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 5 Dec 2001 02:09:54 -0800 From: "Paul Leyland" Subject: RE: Mersenne: p-1 records > Is this a bug in the reporting software? I don't have the > tools to work it out exactly, but a 103-bit number should be slightly larger > than 2^103, or Nope. A 103-bit number N should lie in the range 2^102 <= N < 2^103. > Something really odd is going on. Perhaps this small example will make things clearer: N(dec) N(bin) bits 1 1 1 2 10 2 3 11 2 4 100 3 5 101 3 6 110 3 7 111 3 8 1000 4 9 1001 4 10 1010 4 11 1011 4 12 1100 4 13 1101 4 14 1110 4 15 1111 4 16 10000 5 ... Paul _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 5 Dec 2001 06:09:18 -0600 (CST) From: ribwoods@execpc.com Subject: Re: Mersenne: Re: Factoring benefit/cost ratio Brian Beesley wrote: > On 3 Dec 2001, at 20:38, ribwoods@execpc.com wrote: [... snip ...] > > I think our record shows that a verified factor is still > > slightly (by a minute but nonzero margin) more reliable an > > indicator of compositeness than two matching nonzero LL > > residues. > > AFAIK our record does _not_ show any such thing. Oh? It doesn't? If our record does _not_ show that a verified factor is more reliable an indicator than DC LLs, then what does it show as the (higher, according to this hypothesis) error rate for verified factors? Is the observed error rate in reported factors as great as the ~1-1.5% error rate in reported LL results? How often does double-checking a reported factor find that the reported factor was in error? > In _theory_ there is a very small chance that we _may_ have accepted > an incorrect residual even after double-checking. There is a small > chance in such a case that the residual should have been zero, i.e. > we missed a Mersenne prime. ... and my contention is that those small chances, for L-L results, exceed the corresponding probabilities in the case of a reported factor. There is a small chance that we may accept an incorrect factor even after double-checking it, but that chance is even smaller than the small chance that we may accept an incorrect double-checked L-L residual. > I've triple-checked thousands of small exponents - some of the > ones where the accepted residual was recorded to only 16 bits or > less, which makes the chance of an undetected error _much_ > greater (though still quite small) - so far no substantive errors in > the database have come to light. A very few (think fingers of one > hand) instances of incorrectly matched residuals have come to light - - How does that compare to the observed rate of incorrect factors discovered after triple-checking _them_? > > Some error sources would be more likely to affect the longer LL > > test than the shorter factor verification.) > > Indeed - if errors occur at random intervals, results should get > less reliable as runs take progressively longer. ... and L-L verification runs take a lot longer than factor verification runs, so we can reasonably expect that this class of error will affect L-L verification runs (and thus lower such runs' reliability) a lot more than they do factor verification runs, all else being equal (such as use of the same hardware systems). > However there does seem to be a wide variation in the reliability > of systems. Some seem to have a lot of problems, some very few > (if any). So, while a factor verification run on a system that has a lot of problems may be less reliable than an L-L verification run on a system that has very few or no problems, if we were to compare L-L verification and factor verification runs on the same system or on systems of equal problem probability, we would expect to find that errors whose rates were proportional to time would affect the L-L verification runs more than the factor verification runs because of the significant difference in average run times between the two categories, making the L-L verification runs less reliable than the factor verification runs. Agreed? > I've detected four problems on my own systems so far; two of these > were caused by a failed cooling fan on a P100 system (unlike > current systems, the cooling was _almost_ sufficient even without > forced ventilation); one was caused by a configuration error - > running Glucas on an Alpha system I inadvertently allowed "fast" > arithmetic and turned off error checking, which was a really stupid > thing to do on a system with a 53-bit mantissa FPU - as this was a > QA run on a 33 million range exponent, I was lucky to lose only 3 > months work. The last one I never got to the bottom of, but I > strongly suspect that Prime95's workspace memory was clobbered > during a software installation on a Windows 98 system. How many of those problems caused errors during L-L verifications, and how many caused errors during factor verifications? However, you may not have spent anywhere near as much time doing factor verifications as you have doing L-L verifications, so it may not be valid to draw any conclusion about comparative error rates on your system. Richard B. Woods _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ End of Mersenne Digest V1 #914 ******************************