Mersenne Digest Sunday, September 9 2001 Volume 01 : Number 881 ---------------------------------------------------------------------- Date: Fri, 7 Sep 2001 11:43:28 +0100 From: "Lawrence Cairns-Smith" Subject: Mersenne: Windows ME System Restore This is a multi-part message in MIME format. - ------=_NextPart_000_0001_01C13792.5A75B160 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Hi group, I used the ME system restore utility today for the first time - I thought it would only restore the registry but it also restored the ini files. (my prime directory is c:\windows\system\mersenne - is this why????) I noticed this as my machine started at 0% on a number it had handed in yesterday. I thought people should be aware - if you need to use a restore point then it may be necessary to edit the worktodo.ini file to match the p and q files in the Prime95 directory. Regards, Lawrence.. .. http://www.songwriterscafe.co.uk - ------=_NextPart_000_0001_01C13792.5A75B160 Content-Type: text/html; charset="us-ascii" Content-Transfer-Encoding: quoted-printable

Hi group,

I used the ME system restore utility today for the = first time – I thought it would only restore the registry but it also = restored the ini files. (my prime directory is c:\windows\system\mersenne – is this = why????)

I noticed this as my machine started at 0% on a = number it had handed in yesterday.

I thought people should be aware – if you need = to use a restore point then it may be necessary to edit the worktodo.ini file = to match the p and q files in the Prime95 directory.

Regards,

Lawrence……

http://www.songwriterscafe.co.uk

- ------=_NextPart_000_0001_01C13792.5A75B160-- _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 07 Sep 2001 20:35:19 -0400 From: George Woltman Subject: Mersenne: Version 21.3 (a.k.a release candidate 1) Hi all, Version 21 is close to being official. This version fixes the P4 error recovery bug and the mprime crashes on P4 bug. You can download it at http://www.mersenne.org/freesoft.htm All version 21.2 users will eventually want to upgrade to version 21.3. Version 21.3 is capable of skipping the P-1 factoring step if it has already been run. Of course, you can wait until 21.3 is official rather than just a release candidate. Enjoy, George _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 8 Sep 2001 02:16:32 GMT From: Peter-Lawrence.Montgomery@cwi.nl Subject: Mersenne: All Cunningham Wanted Numbers Factored All Cunningham Wanted Numbers Factored Peter Montgomery pmontgom@cwi.nl September 7, 2001 The Cunningham tables have factorizations of b^n +- 1 for small b and n. The full reference is John Brillhart, D.H. Lehmer, J.L. Selfridge, Bryant Tuckerman, and S.S. Wagstaff, Jr., "Factorizations of b^n +- 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers", Contemporary Mathematics, Volume 22, American Mathematical Society. http://www.cerias.purdue.edu/homes/ssw/cun/index.html The first edition appeared in 1983 and the second in 1988. Sam Wagstaff, the principal maintainer of the tables, is sending a third edition to the publisher this month. TRADITION OF WANTED NUMBERS One Cunningham project tradition has been lists of wanted numbers, usually chosen by author John Selfridge. These have served as challenge numbers -- somebody who claims a superior factoring algorithm will typically demonstrate it on these numbers, which have resisted repeated attempts by others. Pages lviii-lix of the 1983 edition list 10 "most wanted" numbers and 15 "more wanted" numbers. The largest of these is the 71-digit repunit (10^71 - 1)/9. All were factored within about two years, usually by the just-discovered quadratic sieve or by P-1. Page lxxxvi of the 1988 edition lists 10 "most wanted" numbers and 22 "more wanted" numbers, the smallest being the 86-digit number (3^199 - 1)/(2 * 1360648969) and the largest being the 148-digit cofactor (2^512 + 1)/2424833 of the Fermat number F9. All of these were later factored, usually by the elliptic curve method (ECM), multiple-polynomial quadratic sieve (MPQS), or number field sieve (NFS). The F9 factorization made international headlines. The wanted lists have been revised many times between printed editions, approximately annually, as existing entries are factored. The largest number to ever appear, a 291-digit cofactor of F10 = 2^1024 + 1, was factored in October, 1995, when Richard Brent found a 40-digit factor by ECM. The May 31, 2001 list has 10 "most wanted" numbers and 16 "more wanted" numbers, ranging from 144-digit cofactors of 2^631 + 1 and 2^617 + 2^309 + 1 to the 193-digit number (11^191 - 1)/195867 . [There had been 34 wanted entries in July, 2000 -- the other 8 were factored before May 31.] ENTIRELY NEW LISTS The publication of the 3rd edition starts a new era. For the first time since the 1983 edition appeared, the old lists have been completed en masse. All 26 numbers on the May 31 lists were factored by September 7, or 99 days later. The average pace was one number completed every four days. The following individuals contributed to this effort: Bruce Dodson, Lehigh University, Bethlehem, PA, USA Jens Franke, Institute for Pure Mathematics, Bonn, Germany Torbjorn Granlund, Swox, Stockholm, Sweden Thorsten Kleinjung, Institute for Pure Mathematics, Bonn, Germany John Klos Arjen Lenstra, Citicorp, NY, USA (home in NJ) Paul Leyland, Microsoft Research, Cambridge, UK Peter Montgomery, Microsoft Research, Redmond, WA, USA (home in CA) Robert Silverman, Bedford, MA, USA Herman teRiele, CWI, Amsterdam, The Netherlands We used computer facilities at Centrum voor Wiskunde en Informatica (CWI), Amsterdam, The Netherlands High Performance Computing Center North, Stockholm, Sweden Institute for Applied Mathematics, Bonn, Germany Institute for Pure Mathematics, Bonn, Germany Lehigh University, Bethlehem, PA, USA Microsoft Research, Cambridge, UK RSA Security, Bedford, MA, USA SARA, Amsterdam, The Netherlands Stockholm University, Department of Mathematics, Stockholm, Sweden Swedish Institute of Computer Science, Stockholm, Sweden Swox, Stockholm, Sweden plus some home PCs (including a laptop during intercontinental flights!). Only one of the 26 wanted numbers had a prime factor under 47 digits. That number, a c168 cofactor of 3^382+, left a c127 when its 42-digit factor was found by ECM. All other factors were found by SNFS. One wanted number had two factors over 90 digits: 2,619+ = 3 * p91 * p96 p91 = 125738815991080426576344660082527825631801224969 \ 7661907431303034629811311740864601663325811 p96 = 576735513593459498091224888775105070536100466874 \ 272552892992673568274909599171018374973329229033 This is just below the previous size record 10^211 - 1 = 3*3*p93*p118. Both are dwarfed, however, by the new factorization 2^727 - 1 = p98 * p122 p98 = 1760629171181543403793488187233161167077749116644 \ 5300472749449436575622328171096762265466521858927 p122 = 400994997261837585178919394286016657070637945934 \ 4394068988852655680258152926272814339895974344415 \ 0539520890742947533452401 Although 2^727 - 1 is not on the May wanted list, it has long been the first entry in the 2^n - 1 table with no known prime factor. Now that honor goes to 2^751 - 1, followed by 2^809 - 1 and 2^971 - 1. QUICK LINEAR ALGEBRA TO THE RESCUE This effort had factored 19 of the 26 wanted numbers as of August 23, when Sam Wagstaff announced an August 31 freeze date for contributions to the third edition. At that point, several of the remaining wanted numbers were almost sieved, but the linear algebra had been taking 1-2 calendar-weeks per number, pushing their projected completion dates past the August 31 deadline. SARA, a Dutch High-Performance Computing Center in Amsterdam, had been down August 13-20, to enlarge its network (teras) of shared memory 500 MHz MIPS R14000 processors. Peter Montgomery had written a parallel MPI-based version of his Block Lanczos linear algebra code earlier in 1999-2001. Happily, this code functioned well on the new hardware configuration, There was little system downtime, enabling many linear algebra jobs to be run during the crisis period. The recently added teras capacity meant there were short waits for jobs to run. The largest matrix run on teras, for 2^727 - 1, was 3847967 x 3862821. This took 99153 real-time seconds (about 27.5 hours) using 25 processors. The estimated single-processor time is 1200000 seconds (330 hours) for that same matrix on the same hardware, so the job got almost 50% utilization of the 25 processors. By the morning of August 31, eight days after Wagstaff's freeze announcement, we had completed 23 of the 26 wanted numbers, in addition to 2^727 - 1 and some early holes (likely candidates for new wanted numbers). Then Wagstaff announced that Selfridge was on vacation, unable to revise the wanted lists at this time, and gave us approximately one more week to submit results. One more wanted factorization, 2^641 + 1, arrived later on August 31. The last two wanted numbers, cofactors of 2^641 - 1 and 5^283 + 1, had undergone little sieving prior to Wagstaff's freeze announcement. [Conrad Curry had been sieving 2^641 - 1 a year earlier, but none of us had been able to contact him -- we waited until his school year began August 20 before restarting it.] We sieved these last two numbers madly, spreading the effort over several sites. By September 2, we had enough sieving data for 2^641 - 1 -- its factorization was found two days later, with the linear algebra taking 12 wall-clock hours on 16 processors for a 2.548 M x 2.551 M matrix. 5^283 + 1 took longer -- we sieved until September 5, the first convenient date for contributors to merge their data. Collectively we had gathered 10% more relations than needed. Only 5.67 M relations survived the first round of filtering, compared to a typical 8 M or more. A quick but sloppy second stage of filtering left a 2.920 x 2.960 matrix, which 25 teras processors finished in 14 hours. The factorization was found at 03:50 UTC on September 7, about 27.5 hours after the last data file had reached CWI, when one of four square root jobs found a non-trivial factorization. When we submitted 2^641 - 1 to Wagstaff, we checked that he had all wanted factorizations except 5^283 + 1. Alas, Wagstaff lacked 3^386 + 1. That had been done two weeks earlier, but nobody had sent the result to Wagstaff. The oversight was quickly remedied. During those final days, we also finished 11,407M, a 130-digit cofactor of 11^407 + 1 and the then-smallest composite cofactor in the new table. This factorization used the polynomial f(X) = X^5 - 9*X^4 - 16*X^3 + 53*X^2 + 37*X - 23 with root m = 4 + 11^(-18) + 11^19. The smallest composite cofactor in the 3rd edition is another c130, compared to c51 in the 1983 edition and c80 in the 1988 edition. While the 5,283 + 1 linear algebra was running, activity remained busy on other fronts. Jens Franke found a 44-digit factor of 2^1120 + 1 by ECM. The 112-digit cofactor was prime and didn't need more work. Then Paul Leyland, Sam Wagstaff, Alec Muffett, Bruce Dodson, and Arjen Lenstra set a MPQS record. They split a 135-digit cofactor of 2,1606L (which divides 2^803 - 2^402 + 1 and 2^1606 + 1) into 66- and 69-digit prime factors. The prior MPQS champions were RSA-129 (the original challenge number for the RSA cryptosystem, many contributors) and the c127 (90! + 1)/1381173038633 by Sean Irvine. Within the Cunningham table, the old records are two 124-digit numbers by Jens Franke. Leyland et al allowed three large primes, as did Franke. _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 8 Sep 2001 02:27:18 GMT From: Peter-Lawrence.Montgomery@cwi.nl Subject: Re: Mersenne: M727 factored! "Daran" asks > Is M751 now the smallest unfactorised composite Mersenne? What is the > smallest Mersenne not completely factorised? M751 and M809 are the first Mersennes with no known factor. The first holes in the 2^n - 1 table are 2,673- c151 and 2,683- c203. This means, for example, that 2^673 - 1 is partially factored, but it has a 151-digit composite cofactor. The first holes in the 2^n + 1 table are 2,647+ c169 and 2,653+ c154. The first holes in the 2LM table are 2,1238L c160 and 2,1238M c145. These denote cofactors of 2^619 - 2^310 + 1 and 2^619 + 2^310 + 1, both of which divide 2^1238 + 1. Below are ten recently found factorizations. Algebraic factors, such as the factors 23 and 89 of 2^671 - 1 (these divide 2^11 - 1, which in turn divides 2^671 - 1) do not appear. Factors above the * lines were previously known. Peter Montgomery pmontgom@cwi.nl September, 2001 C(2,619+) * c186 = p91.p96 1257388159910804265763446600825278256318012249697661907431303034629811311740864601663325811 576735513593459498091224888775105070536100466874272552892992673568274909599171018374973329229033 C(2,632+) 286297736737 * c177 = p66.p111 471211668918301561515489208246219513333426679953187468148445645729 514032034228747931945571962470228019101894473686825197910636442532520433593399910044880487939432413264840902977 C(2,641+) 1283 32051 139739 353833 1078163 * c169 = p59.p110 73819843823154749726309925820314356063695778208135055585507 18795947089943685289042850201861326689719641302766796883477502913493254840480457593719603600834006204492522841 C(2,641-) 35897 49999 1173835097 2401258891949526685926151441 * c148 = p69.p79 745276300734440606226386924312213175677903182797334854064486587296999 2420161564200739329410254310444778820196576654139080232429544162649795567983079 C(2,643-) 3189281 * c188 = p71.p117 22532429052605670225026391054393428833168207234802434915090881303620353 507909591297683949138862971271266635431758872031092542127980551589004038646657157217329569167343063743426799521984799 C(2,671-) 116356769 33491655209 64110547427930873 * c145 = p68.p78 13646560594525825890627182668772241639702837721889959372317451952089 608833519146176962786346063898868909094632504100539398786357475514441579020823 C(2,727-) * c219 = p98.p122 17606291711815434037934881872331611670777491166445300472749449436575622328171096762265466521858927 40099499726183758517891939428601665707063794593443940689888526556802581529262728143398959743444150539520890742947533452401 C(2,1202L) 7213 * c178 = p87.p91 322191336498946329196503049475322564558677154558189688098324958943433876457693205092709 3571063752373727959434120513220011301363863161567383982128636656862221716975343445451820353 C(2,1222L) 1363753 * c161 = p69.p92 390941529316414655423854492083019690148253103500590794058313678419233 70215922956051621713037377195110638684576079957295845924735328290270267776117780526372201309 C(2,1234M) 86381 7367588575848411802768597653205046693 * c144 = p56.p88 25030363534817185101957125006047751030454874478028239473 6828519750766734356393222104746037438762841641726469993132504189166732581463128027874013 _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 8 Sep 2001 18:11:41 -0000 From: bjb@bbhvig.uklinux.net Subject: Re: Mersenne: All Cunningham Wanted Numbers Factored Hi, Coincidentally to Peter's message, and as an encouragement to anyone else working in this field, it just so happens that one of my systems discovered a previously unknown (AFAIK) factor of one of the Cunningham Project numbers yesterday evening: [Fri Sep 07 21:33:06 2001] ECM found a factor in curve #199, stage #2 Sigma=6849154397631118, B1=3000000, B2=300000000. UID: beejaybee/Simon2, P1136 has a factor: 9168689293924594269435012699390053650369 Factors this size aren't too easy to find, but (despite the subject line in Peter's message) there are still a large number of candidates which need work done on them. FWIW if you have a dual CPU system (mine is running 2 * PIII-850 on a Supermicro P6DBE m/b), running ECM on small exponents on one processor makes an ideal foil to running LL tests on the other. The ECM process uses so little memory that it runs practically in the L2 cache, except during Stage 2. The LL test will slow down a bit during ECM stage 2, but that's only about 30% of the time - whereas running LL tests on both processors can slow both processes down quite substantially due to the loading on the memory bus. BTW this was found with Prime95 v21.2, so I guess that's another check mark on the QA table: ECM _does_ find factors! Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 8 Sep 2001 13:36:03 -0600 From: "Matt Goodrich" Subject: Mersenne: Prime Net Server This is a multi-part message in MIME format. - ------=_NextPart_000_0001_01C1386B.3611B1F0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Is there scheduled maint. going on with the server today, or is this a unscheduled outage? Matt - ------=_NextPart_000_0001_01C1386B.3611B1F0 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

Is = there scheduled=20 maint. going on with the server today, or is this a unscheduled=20 outage?

Matt

- ------=_NextPart_000_0001_01C1386B.3611B1F0-- _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 08 Sep 2001 21:15:57 -0700 From: Gerry Snyder Subject: Re: Mersenne: All Cunningham Wanted Numbers Factored bjb@bbhvig.uklinux.net wrote: > > Hi, > > .... > > FWIW if you have a dual CPU system (mine is running 2 * PIII-850 > on a Supermicro P6DBE m/b), running ECM on small exponents > on one processor makes an ideal foil to running LL tests on the > other. Ditto on my dual PIII-1GHz. > The ECM process uses so little memory that it runs > practically in the L2 cache, except during Stage 2. The LL test will > slow down a bit during ECM stage 2, but that's only about 30% of > the time - And the slow-down is not very significant--seems to be less than 10%. > whereas running LL tests on both processors can slow > both processes down quite substantially due to the loading on the > memory bus. Definitely. About 30% on each processor here. Meaning I used to have about 1.4 processor-equivalents when both were doing LL. Now I have close to 1.0 doing LL and another 1.0 helping to find factors. Seems better overall. Perhaps a Mersenne number I would have got will be shown to be prime. So be it. It is a thrill to be able to contribute to this effort. Gerry - -- mailto:gerrysnyder@mediaone.net Gerry Snyder, AIS 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.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 09 Sep 2001 01:58:03 -0700 From: "Terry S. Arnold" Subject: Mersenne: Time Algorithm What is the correct algorithm for calculating the time credit for a LL test of an exponent? I did a linear interpolation from the times in the status page and this does not match reality. When I think about the growth characteristics of a FFT it appears that my approximation was naive. Regards Terry _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 09 Sep 2001 12:00:19 -0400 From: George Woltman Subject: Re: Mersenne: Time Algorithm Hi Terry, At 01:58 AM 9/9/2001 -0700, Terry S. Arnold wrote: >What is the correct algorithm for calculating the time credit for a LL >test of an exponent? Take the timing on the status page, multiply it by the exponent. That gets your the PII-400 timing in seconds. Divide by (86400 * 365). That gets you the timing in CPU-years. Multiply by 5.5, the conversion factor from PII-400 CPU-years to P90 CPU-years. >I did a linear interpolation from the times in the status page and this >does not match reality. When I think about the growth characteristics of a >FFT it appears that my approximation was naive. I can interpret your question two ways: 1) You were expecting timings to increase linearly within a FFT range. This is not the case, all exponents from 10.33M to 12.83M take the same time per iteration. 2) You expected a 512K FFT timing to be twice the 256K FFT timing. This is not so for a variety of reasons. a) The FFT algorithm is O(N log N). So the 512K FFT should be 512K*log(512K)/(256K*log(256K)) = 2 * 19/18 slower. b) More importantly, the CPU caches work less effectively as the FFT gets larger. A 64K FFT can fit within some CPU's L2 caches. Jumping to a 128K FFT means half the data is in the L2 cache and half is in main memory (when switching from pass 1 to pass 2 of the FFT). c) At these large FFT sizes, we are now putting pressure on the TLB caches. The TLB maps a virtual address into a physical address. Intel chips keep track of 64 TLB entries, each entry maps to a 4KB page. IIRC, Athlon CPUs have an even smaller TLB cache. A TLB cache miss does add some time to a memory access. Regards, George _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ End of Mersenne Digest V1 #881 ******************************