Mersenne Digest Tuesday, 28 April 1998 Volume 01 : Number 352 ---------------------------------------------------------------------- From: Will Edgington Date: Sun, 26 Apr 1998 13:31:28 -0700 Subject: Mersenne: P-1 factoring "meta-info" #2 Presently, the available ranges are 2000 thru 2700, 6000 thru 8190, 16418 thru 20000, 32000 thru 86000, and almost everything above 87000. I have no save files for any exponents. I now have 12 save files for exponents under 1000 and ten of them are for the ten smallest incompletely factored exponents thru a stage one bound of 120,000,000; those ten exponents are now available for reservation, which I will do under the proposal I metioned yesterday to see how well it works: Lastly, there has been a proposal to randomly assign exponents under 1500 or so one per computer at a time so that more people have the chance to factor the smallest incompletely factored exponents. So, if you want to work on one of the last ten exponents under 727, send me email and I'll reply with the Factor98 save file. If ten or more people are quicker than you are, I'll keep your name on my list, send you an exponent (or exponents if you have more than one computer) between 2000 and 2700, or both; please indicate which of the three you want me to do. Will ------------------------------ From: Michiel van Loon Date: Mon, 27 Apr 1998 00:53:48 +0200 Subject: Mersenne: New version of PRIMEOS2 available New versions (3.0.1) of PRIMEOS2 and PRIMEEMX have been uploaded to http://www.xs4all.nl/~mfvl/prime Changes to v3.0: replaced the old factoring code by the latest version. NOTE: ===== It is only needed to replace your current version of PRIMEOS2 if you are using a AMD K6 processor. It appears you could get a SIGILL exception while factoring. This has been corrected. Intel processors are not affected by this change. ------------------------------ From: Peter-Lawrence.Montgomery@cwi.nl Date: Mon, 27 Apr 1998 03:39:57 +0200 (MET DST) Subject: Mersenne: M(589) factored M(589) has been the first incompletely factored M(n) = 2^n - 1. Now that distinction goes to M(601). The factors of M(589) are M(19) = 524287 M(31) = 2147483647 18083479 36064471 p46 = 2023706519999643990585239115064336980154410119 p103 = 13635133929781911357360183447731257848357221022119139\ 63639355051056896705852735103386975412732016027769 The p46 was found on an SGI Origin workstation with R5000 processor at 04:26 Saturday April 25, 1998, using the elliptic curve y^2 == x^3 + Ax^2 + x (mod p46) where A == 780120419943404649432897790365517824268303676 (mod p46). The group order is 2023706519999643990585250126089270445504437408 = 2^5 * 3 * 7^2 * 223 * 661 * 2141 * 2621 * 847031 * 5965699 * 6047191 * 17020639711 . The stage 1 limit was 8 million, slightly larger than the two factors near 6 million. The factorizations of p46 -+ 1 are p46 - 1 = 2.7.19.31.53.181.641.39910918849486318887656194928323841 p46 + 1 = 2.2.2.3.3.3.5.17.97.1136326460480899754388315654304705983511 (the periods denote multiplication). The p46 could not have been found by P-1. Since September, 1997, we have learned the factorizations of M(n) for several n < 700: Prime exponents Composite exponents 569 NFS 581 NFS 571 NFS 589 ECM 593 NFS 623 NFS 599 ECM 635 NFS 613 ECM 659 ECM 661 ECM (ECM = elliptic curve method, NFS = number field sieve). It remains to complete M(n) for n = 601, 617, 619, 631, 641, 643, 673, 677, 683 (prime exponents) 611, 629, 667, 671, 679, 689, 695 (composite exponents) ------------------------------ From: Walt Mankowski Date: Sun, 26 Apr 1998 22:37:05 -0400 (EDT) Subject: Mersenne: Upgrading Machine In the next week or two, one of the machines I'm currently running prime95 on is getting upgraded. It's going from a Pentium 150 to a Pentium-II 333, so of course I'm looking forward to a huge performance increase. Is there any problem with starting an exponent with one machine and finishing it with another? Or can I just save off the current directory, copy everything to the new machine, use the menu to update the ini file with my new machine type, and restart it? Walt Mankowski wmankows@qvc.com ------------------------------ From: Eric Brier Date: Mon, 27 Apr 1998 10:21:20 +0100 Subject: Re: Mersenne: Lucas-Lehmer test idea If you calculate N mod p mod q it is a mathematical non-sense ( see below ) and further more, it is impossible to calculate it without computing N mod p !!! You idea is a good one because many algorithms compute modulo little primes but in this case, it is impossible. Sorry .... Why is it a non-sense ? N mod p is not a number but a list of number in arithmetical progression of step p and since p and q are primes, you get all residues mod q for a same number N .... Eric brr@ingsud.dga.fr ------------------------------ From: Peter-Lawrence.Montgomery@cwi.nl Date: Mon, 27 Apr 1998 12:21:40 +0200 (MET DST) Subject: Re: Mersenne: Lucas-Lehmer test idea Eric Brier writes: > If you calculate N mod p mod q it is a mathematical non-sense ( see > below ) and further more, it is impossible to calculate it without > computing N mod p !!! > You idea is a good one because many algorithms compute modulo little > primes but in this case, it is impossible. Sorry .... > > Why is it a non-sense ? > > N mod p is not a number but a list of number in arithmetical > progression of step p and since p and q are primes, you get all residues > mod q for a same number N .... If we have good bounds on the size of an integer N, we might compute (N mod p1), (N mod p2), ... (N mod pk) for several primes p1, p2, ..., pk such that p1 * p2 * ... * pk > (bound on N). These remainders determine N uniquely if we further know N >= 0 (otherwise, double the bound). Once we know N, (N mod q) can be found. It is possible to arrange the latter computations to get (N mod q) without determining N directly. For the LL test, this is not very useful. Each iteration of LL doubles the number of digits in the residual, if we do not reduce it modulo M(p). The bound on the final residual is about 2^p digits, which is 2^4000000 digits for values of p being done today. It is impractical to use several moduli whose product is close to 10^(2^4000000). ------------------------------ From: Nick Craig-Wood Date: Mon, 27 Apr 1998 12:18:38 +0100 (BST) Subject: Re: Mersenne: Lucas-Lehmer test idea On Mon 27 Apr, Eric Brier wrote: > If you calculate N mod p mod q it is a mathematical non-sense [snip] > N mod p is not a number but a list of number in arithmetical > progression of step p and since p and q are primes, you get all residues > mod q for a same number N .... Yes you are right! [p isn't necessarily a prime (we are trying to prove that) and q needn't be a prime (I was thinking of using 2^n) but gcd(p,q) is certainly 1 if we are attempting the LL test.] - -- Nick Craig-Wood ncw1@axis.demon.co.uk http://www.axis.demon.co.uk/ ------------------------------ From: GivenRandy Date: Mon, 27 Apr 1998 08:40:00 EDT Subject: Re: Mersenne: Upgrading Machine > Is there any problem with starting an exponent with one machine and > finishing it with another? Or can I just save off the current > directory, copy everything to the new machine, use the menu to update > the ini file with my new machine type, and restart it? That should do it. You want to make sure the Pnnnnnnn and Qnnnnnnn files are copied (which copying the whole directory will do). Then double-check your settings (i.e., ini file), and you're set to blow away your previous productivity values. Randy Given GivenRandy@aol.com http://members.aol.com/GivenRandy public key at http://members.aol.com/GivenRandy/pgpkey.asc ------------------------------ From: George Woltman Date: Mon, 27 Apr 1998 10:17:28 -0400 Subject: Re: Mersenne: Rolling Average At 09:18 PM 4/25/98 -0400, Walt Mankowski wrote: >What does the "RollingAverage" field in local.ini field mean? RollingAverage is set based upon whether your computer is faster or slower than expected. RollingAverage starts at 1000. If your machine is faster than expected RollingAverage goes up, otherwise it goes down. RollingAverage is used to give a time estimate in the Test/Status dialog box, rollingAverage is also used to send expected completion dates to the PrimeNet server. RollingAverage is computed by measuring the actual time it takes to execture 65536 LL iterations and compare that to how long the prime95 expected 65536 iterations to take. There have been some bugs reported in the computation of the rollingAverage. These will be fixed in version 16 of prime95. Best regards, George ------------------------------ From: "John R Pierce" Date: Mon, 27 Apr 1998 07:47:52 -0700 Subject: Re: Mersenne: Upgrading Machine >> Is there any problem with starting an exponent with one machine and >> finishing it with another? Or can I just save off the current >> directory, copy everything to the new machine, use the menu to update >> the ini file with my new machine type, and restart it? > >That should do it. You want to make sure the Pnnnnnnn and >Qnnnnnnn files are copied (which copying the whole directory >will do). Then double-check your settings (i.e., ini file), >and you're set to blow away your previous productivity values. You probably should delete the entries in whichever .INI file it is that sez the tests have been passed so that it will do the tests on the new system. - -jrp ------------------------------ From: David L Nicol Date: Mon, 27 Apr 1998 11:30:50 -0500 Subject: Re: Mersenne: how to tell? Has anyone looked into symmetries btn early and late iterations? It starts with all ones and ends up with all zeroes, somehow. I wonder if that is all the generalizations that can be made. John R Pierce wrote: > >Ok i am over half way done with my LL test for 4464569 and i want > >to know > if a > >message comes up to tell you that its not a mprime before all the > iterations > >are done? > > > > Nope, it can't tell until the LL test is finished. The LL > definition of primality is that the residual is 000000000...000000 > after the last iteration of the test. ______________________________________________________________________ David Nicol 816.235.1187 UMKC Network Operations david@news.umkc.edu "When I'm trying to get to the other side of town" -- Jimi ------------------------------ From: David L Nicol Date: Mon, 27 Apr 1998 12:07:40 -0500 Subject: Re: Mersenne: Repunit Primes Warut Roonguthai wrote: > > Once there was a good page about generalized repunit primes by one of > GIMPS members (can't recall whom) at > > http://www.rosenheim.baynet.de/~karoli01/pgmprim1.html > > Does anyone know where it is now? Thanks in advance. Someone -- "dejaweb" or something like that -- backs up web pages as a public service. If you can find them they might have it. (it isn't "dejaweb.com" exactly because that web page is an ISP in japan.) I am posting this to the main list because I believe the existence of the service and their proper contact info is relevant and is something we should all know. ______________________________________________________________________ David Nicol 816.235.1187 UMKC Network Operations david@news.umkc.edu "When I'm trying to get to the other side of town" -- Jimi ------------------------------ From: "Charles F. Kerchner III" Date: Mon, 27 Apr 1998 13:18:55 -0400 Subject: Mersenne: Another test other than Lucas-Lehmer All this talk about "calculat(ing) the result of the Lucas-Lehmer test (of p) modulo another number (q)" got me thinking. I was looking at "Pepin's Test" for proving the primality of "Fermat Numbers" and "Miller's Test" for testing "Strong Probable Primes". Hopefully someone can show me if my ideas are true or not, but here goes: Miller's Test for Strong Probable Primes to base b is (from "Primes and Programming: An Introduction to Number Theory with Computing" by Peter Giblin): Let n be an odd integer > 1 and let b be coprime to n. Step 1: Let k = n - 1, b^k mod n = r, If r = 1 then continue, otherwise n "fails" the test. While k is even and r = 1, repeat the following: Step 2: Replace k by k/2 and replace r by the new value of b^k mod n. When k fails to be even or r fails to be 1: If r = 1 or n-1 (which is equivlant to -1) then n "passes" the test. Else if r is not = 1 and r is not = n-1 then n "fails" the test". Pepin's Test for Primality of Fermat's Numbers is (from Eric W. Weisstein's Math/Prime pages): If Fn = 2^((2^n)+1) and n >= 2 and k >=2, the two following conditions are equivalent: 1. Fn is prime and k / Fn = -1 2. k^((Fn-1)/2) = -1 (mod Fn), k is usually taken as 3 as a first test. I noticed (use the Pepin's Test as reference) that for a Mersenne Number Mn = 2^p-1, where p is prime, that k / (2^Mn) = -1 for k = 3. And Mn -1 = 2^p - 2 and (Mn - 1)/2 = 2^(p-1) - 1 (since Mn-1 is even). Therefore if k^((Mn-1)/2) = -1 (mod Mn) then Mn should be prime for k = 3. Plus (use the Miller's Test as reference) for a Mersenne Number Mn=2^p-1, if b^(Mn-1)/2 mod Mn is 1 or -1 then Mn is a strong probable prime. If we use b=3, Miller's test simplies into the following: x = 3; for (i = 0; i < (p-2); i++) { x = (x * x * 3) mod Mn; } This test also take (p-2) steps and looks about as "simple" to code as the "Lucas-Lehmer" test. The questions is: Is there anything we can simplify, to reduce the number of steps the test takes to prove than Mn is at least a strong pseudo-prime? (Like the Miller's Test, it reduces the numbers of steps by 1 for each lower value of k). If we use the Miller's Test in reverse, the aglorithm produces "While k is odd and r = 1 or -1, k = k*2, repeat to k >= n - 1 or r does not equal 1 or -1". The BIG question I have is that I know that there are algorithms for factoring numbers n based on n-1 or n+1. It seems Miller's Test is a derivative of the n-1 tests. I know that the Lucas test is a derivative of the n+1 test. Is there something here that we can combine the n-1 and n+1 tests, to produce a simple test to prove that Mn is a pseudo-prime and if it is, THEN run the complete LL test? Chip Kerchner ------------------------------ From: "Harijs Ausmanis" Date: Mon, 27 Apr 1998 22:26:24 +0300 Subject: Mersenne: A question This is a multi-part message in MIME format. - ------=_NextPart_000_019C_01BD722B.83276840 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Does the chance that the exact potential Mersenne Prime that is tested = at a given moment increase by searching? Meaning, if the exponential = that is tested is not a Mersenne Prime, is it being announced to the = person searching after some iteration in the middle or only in the end = after all the iterations are completed? =20 (Could you please Cc: any replies to harijs@parks.lv ? I can't succeed = at subscribing to the list, yet) _______________________________________________ _________| = |_________ \ | The brain of an average man is 1350 ccm. = | / \ | The brain of an average woman is 1250 ccm. = | / \ | (Guiness Book of = Records) | / \ | = | / > | Never underestimate the power of positive = thinking. | <=20 / | (Might & = Magic IV) | \ =20 / |_______________________________________________| = \ /___________) = (__________\=20 - ------=_NextPart_000_019C_01BD722B.83276840 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable
Does the chance that the exact = potential=20 Mersenne Prime that is tested at a given moment increase by searching? = Meaning,=20 if the exponential that is tested is not a Mersenne Prime, is it being = announced=20 to the person searching after some iteration in the middle or only in = the end=20 after all the iterations are completed?
 
(Could you please Cc: any replies to harijs@parks.lv ? I can't succeed at = subscribing to the list, yet)
          &nbs= p;     =20 _______________________________________________
_________|  =             &= nbsp;           &n= bsp;           &nb= sp;           &nbs= p;            = ;            =       =20 |_________
\         &nbs= p;    =20 |   The brain of an average man is 1350=20 ccm.           &nb= sp;      =20 |            =   =20 /
 =20 \            = =20 |   The brain of an average woman is 1250=20 ccm.           &nb= sp;  =20 |            = =20 /
   =20 \          =20 |            =             &= nbsp;           =20 (Guiness Book of Records)     =20 |           =20 /
     =20 \        =20 |            =             &= nbsp;           &n= bsp;           &nb= sp;           &nbs= p;            = ;        =20 |         =20 /
       =20 >      |       = Never=20 underestimate the power of positive thinking. =20 |        <=20
     =20 /        =20 |            =             &= nbsp;           &n= bsp;     =20 (Might & Magic=20 IV)           =20 |          =20 \       
   =20 /          =20 |_______________________________________________|    =         =20 \
 =20 /___________)          =             &= nbsp;           &n= bsp;           &nb= sp;           &nbs= p;            = ; =20 (__________\
- ------=_NextPart_000_019C_01BD722B.83276840-- ------------------------------ From: "John R Pierce" Date: Mon, 27 Apr 1998 21:38:25 -0700 Subject: Re: Mersenne: Rolling Average >RollingAverage is set based upon whether your computer is faster >or slower than expected. RollingAverage starts at 1000. If your >machine is faster than expected RollingAverage goes up, otherwise it >goes down. RollingAverage is used to give a time estimate in the >Test/Status dialog box, rollingAverage is also used to send expected >completion dates to the PrimeNet server. So mine reading RollingAverage=1235 RollingStartTime=893734586 CPUType=6 CPUSpeed=300 CPUHours=24 OldRollingAverage=1242 indicates my system seems to be faster than expected for a 300MHz CPU? Interesting. Its currently at ~307MHz (77MHz*4), and has accelerated CAS timing set. (Since I removed Crescendo from my system, I haven't suffered any more "ERROR: Sumout"s). But I can't imagine that being worth 1.2X [i.e. 23% faster]! (is that what 1235 means?) - -jrp ------------------------------ End of Mersenne Digest V1 #352 ******************************