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:45:28 +0000 To: Luke Welsh From: mersenne-digest-invalid-reply-address@base.com (Mersenne Digest) (by way of Gordon Spence ) Subject: Mersenne Digest V1 #917 Mersenne Digest Sunday, December 9 2001 Volume 01 : Number 917 ---------------------------------------------------------------------- Date: Fri, 7 Dec 2001 23:12:16 +0000 (GMT) From: Russel Brooks Subject: Re: Mersenne: last call for a santa cruz ride... (was: silicon valley 'prime' dinner) John R Pierce wrote: > is *anyone* going to this dinner? I still plan to launch from Santa Cruz Yeah, we're going but leaving from SJ; see you there! Cheers... Russ Primenet; @909 _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 07 Dec 2001 18:24:58 EST From: EWMAYER@aol.com Subject: Mersenne: Re: Mersenne Digest V1 #916 Alex Kruppa wrote: <<< There is an _excellent_ article on the Heise Newsticker (in german). This is one of the few I've seen that has all the facts right [snip, or should I say, schnipp] http://www.heise.de/newsticker/data/as-06.12.01-000/ >>> Yeah, it's not bad, except that it says Scott K. did the double-check of the newly discovered prime. I knew the PrimeNet server did a lot of nifty stuff, but I've not seen a widget titled "click here to perform a double- check of a newly discovered Mersenne prime." Perhaps in an obscure spot on the manual testing form? :) Just my Zwei Pfennig's worth, - -Ernst _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 07 Dec 2001 18:40:28 EST From: EWMAYER@aol.com Subject: Mersenne: Re: 39. Mersenne-Primzahl Prost Alex Kruppa also wrote: << Steve Harris and I will meet in Munich tonight and have a "Prost!!" to the new prime. 6pm pacific time is 1am MET - let's see if we can stay up to sync with the California crowd for a toast! >> Well, let me see here...Paul Landon and a bunch of other math geeks will be toasting the new discovery in Nu"rnberg at exactly 6:30 California time, so we can toast with you Mu"nchners at 6:00, and that should still leave time to empty our glasses and order a new round in time to toast with Landon & Co. at 6:30. The 7:00 time slot is still free (as if we needed another excuse.) John Pierce wrote: << is *anyone* going to this dinner? I still plan to launch from Santa Cruz around 5pm, and my ride offer is still valid. >> Hey, John - I've gotten a definite "I'll be there" from about 6 other people, it just happens that none are from the Santa Cruz area. Perhaps most surfers just don't have a lot of time for prime hunting. Cheers, - -Ernst _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 07 Dec 2001 17:18:13 -0800 From: Gerry Snyder Subject: Re: Mersenne: Re: 39. Mersenne-Primzahl Prost EWMAYER@aol.com wrote: > > Alex Kruppa also wrote: > > > Well, let me see here...Paul Landon and a bunch of other > math geeks will be toasting the new discovery in > Nu"rnberg at exactly 6:30 California time, so we can > toast with you Mu"nchners at 6:00, and that should still > leave time to empty our glasses and order a new round > in time to toast with Landon & Co. at 6:30. The 7:00 > time slot is still free (as if we needed another excuse.) If any Mersenners want to toast online, and have an IRC client, I have set up a chatroom named #m39 on server irisarian.dynip.com . I will be out until 8:30 or so Pacific time, but all are welcome at any time. Gerry - -- mailto:gerrysnyder@mediaone.net Gerry Snyder, AIS Director & Symposium Chair, Region 15 RVP Member San Fernando Valley, Southern California Iris Societies in warm, winterless Los Angeles--USDA 9b-ish, Sunset 18-19 my work: helping generate data for: http://galileo.jpl.nasa.gov/ _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 7 Dec 2001 21:34:27 -0800 From: "John R Pierce" Subject: Mersenne: GIMPS meet in Mountain View Well, we had a nice get together in Mtn View tonite as planned. We toasted the requisite pitchers of the Tied House's rather excellent Dark and Stout... And we had a surprise visit by Donald Knuth himself. My pictures didn't come out that great, and I thought I took more than I apparently did, but here's what I got... http://hogranch.com/s300/2001-12-07/ note, each picture is on there twice, the original 1600x1200 rather huge files are msotly good for printing (download and save them locally, and load them into a proper graphics program for decent results, web browsers are lousy at printing large picture files), and a -half 800x600 version far more suitable for viewing. - -jrp _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 07 Dec 2001 21:45:21 -0800 From: Spike Jones Subject: Mersenne: Bay area GIMPS party I just got back from the Bay Area GIMPS party at the Tied House in Mountain View, Taxifornia. I had the time of my life. We had the following people attend: Todd Sauke Chris Brown Edith Mailolo Russell Brooks John Pierce Ernst Mayer Brad Bernard Harvald Alvestrand (all the way from Norway) Irv Rosenfeld Shelly Jones Spike Jones Scott Kurowski (who most generously bought dinner for the whole crew) Donald Knuth (yes, THE Donald Knuth) I tried to introduce myself to Professor Knuth, but Im afraid Im not good in the presence of greatness, so I stammered like Ralph Kramden: "Hello professor, Immm hammina hammina hammina... My name issss hammina hammina hammina..." etc. John Pierce took some photos that he will post on his website. Im the skinny blonde goof standing behind Dr. Knuth. Notice there were exactly 13 attendees. Not only is 13 a prime number, it is also the fifth Mersenne prime! Fifth! Five is the Third Mersenne prime! Three is the second Mersenne prime! 2 is the first mersenne prime! And 1 is the only other factor of a Mersenne prime besides itself! What a remarkable coincidence, friends. I am so in awe. What are the chances? Practically unimaginable. Thank you very much Scott Kurowski for dinner and your associates Brad and Chris who came all the way up from San Diego to join our Mersenne soiree. You guys are the best. spike _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 9 Dec 2001 18:35:55 -0000 From: "Daran" Subject: Mersenne: Why is the default page... ... of the GIMPS website http://www.mersenne.org/ a list of other distributed computing projects? By all means link to and support these projects, but wouldn't prime.htm be a more sensible starting point? Regards Daran G. _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 9 Dec 2001 18:35:41 -0000 From: "Daran" Subject: Mersenne: P-1 Stage 2 The math page http://www.mersenne.org/math.htm explains how to do a stage 1 P-1 test with given bound B1, but it omits the explanation of the enhansement that uses B2 in stage 2. Anyone care to explain how this is done? Cheers Daran G. _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 09 Dec 2001 23:08:43 +0100 From: Henk Stokhorst Subject: Mersenne: new stats and updated software L.S., Time to play a little with the stats again. I made a graph of the amount of participating machines based on the following new definition: Blue line: a pc is participating on the day it checked in a result and all days in between the first and last time it checked in a result if it checked in more than one result. A result can either be a LL test or a factor found. Purple line: a pc is participating if it checked in at least one result, the period is extended up to the last day it reported progress on a new assignment to the server. The image can be viewed at: http://home.planet.nl/~tha/primenetnumbers.gif (day 291 is the day of the last server synchronization, day 680 is this Saturday, the stats are based on cleared.txt and status.txt) The program to monitor progress on factoring work done has had a little update. The graph of this weekend can be found at: http://home.planet.nl/~tha/overview20011209.gif The program to create this graphic now shows an empty screen immediately when started, shows the lower and upper border after the first pass and all elements when processing is completed. This makes it look more responsive than the previous version. The Delphi sourcecode in the zipfile can be trown away if not wanted. To use the program run the 'decomp -n lowerlimit upperlimit' utility first. The program can be found at: http://home.planet.nl/~tha/overview.zip YotN, Henk Stokhorst _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 10 Dec 2001 01:16:24 +0100 From: Alexander Kruppa Subject: Re: Mersenne: P-1 Stage 2 Daran wrote: > > The math page http://www.mersenne.org/math.htm explains how to do a stage 1 > P-1 test with given bound B1, but it omits the explanation of the > enhansement that uses B2 in stage 2. Anyone care to explain > how this is done? > > Cheers > > Daran G. P-1 stage 1 computes x = a^E (mod N), where E is the product of all primes and prime powers <= B1. If stage 1 does not find a factor, gcd(x-1, N) = 1, we go to stage 2. The idea behind a second stage for P-1, P+1 and ECM is that a random number will usually have its biggest prime factor quite a bit larger than the second biggest, so it is worthwhile to figure something out to include a single big prime more quickly. We can go from x^p_i to x^p_{i+1}, where p_i is the i-th prime, quickly by multiplying by x^(p_{i-1} - p_i). The difference between consecutive primes is relatively small, apparantly no bigger than (log(B2)^2),so we have no problem precomputing x^n for even n to cover all the possible differences of consecutive primes we're having in our stage 2. For each x^p_i we compute this way, we multiply this x^p_i-1 to an accumulator. We find the factor f of N if there is a prime p within our stage 2 interval so that f-1 | E*p (more specifically, ord(a) mod f | E*p), since then a^(E*p) - 1 == 0 (mod f), thus the accumulator == 0 (mod f) and a final gcd will reveal f. We get something like: (x is assumed intact from stage 1) xn[j] = x^(2*j), 1 < 2*j < max(p_{i+1} - p_i), p_{i+1} <= B2 last_p = last prime done in stage 1 for B1 < p <= B2, p prime x = x * xn[(p - last_p)/2] accu *= x-1 last_p = p print gcd(accu, N) This needs two multiplies per prime in the stage 2 interval, as opposed to about 20 squarings (for a prime around 2^20) if it had been included in stage 1. We can speed that up further. x^n - x^m = x^m (x^(n-m) - 1), thus we can get the (x^p - 1) we want by a single subtraction if we can write p as n-m. (The extra x^m factor on the right side does not hurt.) For example, for D ~= sqrt(B2-B1) store values xm[i] = x^i, 1 <= i < D and xD[i] = x^(i*D) , B1/D < i < B2/D+1 Since we have only odd p, we can make D even and store xm only for odd i. Now we can do for B1 < p <= B2, p prime accu *= (xD[i] - xm[j) where Di-j = p print gcd(accu, N) Thus we need only one multiply per prime in the stage 2 interval, aside from the about 2*sqrt(B2-B1) multiplies in setting up the tables. However, we need more storage for precomputed values. It can be done even faster, by pairing up primes, which can reduce the number of multiplies again by almost half. The definitive source for info on these algorithms is Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. Vol. 48, 1987, pp. 243-265. There are other enhancements that are even faster but require much more memory (and which I don't quite understand), try P. Montgomery & R. Silverman, An FFT extension to the P-1 factoring algorithm, Math. Comp. Vol. 54, 1990, pp. 839-854, also available online at ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz . BTW, Prime95 uses the one-multiply variant with prime-pairing, plus something stange called "Suyama's powers" (don't ask me), for both P-1 and ECM. Alex _________________________________________________________________________ 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 #917 ******************************