Mersenne Digest Thursday, 28 May 1998 Volume 01 : Number 368 ---------------------------------------------------------------------- From: David Hamer Date: Tue, 26 May 1998 09:24:55 -0400 Subject: Mersenne: Error message Since installing and running v16.3.1 of Prime95 I have begun to encounter the following error message: "Error writing intermediate file: r4649153" ...which I have not seen while running several earlier versions. The program continues to run OK in spite of this and the 'p' and 'q' temporary files are created on schedule. Comments/solutions appreciated. DHH ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ David Hamer                 PGP public key on request dhamer@eclipse.net   or     hamer@gibraltar.ncsc.mil   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ------------------------------ From: "Tim Charron" Date: Tue, 26 May 1998 09:24:08 -0400 Subject: (Fwd) Re: Mersenne: Squareroot of Integers Forwarded message: From: Self To: Eric Brier Subject: Re: Mersenne: Squareroot of Integers Reply-to: tcharron@ctfinance.com Date: Mon, 25 May 1998 16:14:45 -0400 Eric Brier wrote: > The fastest way to obtain the integer part of the squareroot of n is to > compute : > (x*x+n*n)/(2*x*n) ---> x until x is stable or makes flip flop between > two consecutive values. You can start from any non zero integer. It is > quite simple and very fast. I think you mean: (x*x+n)/(2*x) ---> x - -- Tim Tim Charron tcharron@ctfinance.com tcharron@interlog.com ------------------------------ From: George Woltman Date: Tue, 26 May 1998 09:45:58 -0400 Subject: Re: Mersenne: Locking out factoring assignments on v16.3.5 Hi all, Rick Pali's problem has been fixed. He will now get the LL assignments he expects. It was fixed on the server, you do not need a new executable. At 09:14 PM 5/25/98 -0400, Brian Beuning wrote: >I noticed a little unexpected behavior when we switched from >version 15 to 16. Each machine had two exponents checked out, >call them A and B. On version 15, they had been crunching >away on the LL test for A. When we switched to version 16, >they started trying to factor B. When they were done factoring >B they resumed the LL test on A. Then I assume it is going to >do the LL test for B. This is normal and version 15 did the same thing. Prime95 makes sure all the entries in worktodo.ini are fully factored before starting or continuing a Lucas-Lehmer test. The program does this to ensure that there is enough work queued up (if the program expected a test to take 3 weeks but factoring eliminated it in 30 minutes, then your computer could be idle until your next connection to the Internet). As an aside, version 16 does a little more factoring than version 15 did. This is probably why Brian noticed this behavior now. At 10:03 PM 5/25/98 -0500, Mikus Grinbergs wrote: >Rick said he asked for one day's worth of work to do. Perhaps the >server thought that _any_ LL test it had would take more than that. Setting days of work to get to 1 day does not stop prime95 from getting LL tests from the server that take weeks to complete. Perhaps days-of-work-to-get would be better named make-sure-I-have-at-least-this-many-days-of-work-queued-up-at-all-times. Set this value to the maximum number of days your computer will be running without connecting to the Internet. Best regards, George ------------------------------ From: Ken Kriesel Date: Tue, 26 May 1998 23:19:15 -0500 Subject: Mersenne: size of intermediate files Here are the sizes of intermediate save files for Prime95 v16.3 All sizes in bytes, prime95 or NTprime, on Win95 or NT system. This might occasionally be of help in identifying cases where a file of the wrong size has been produced. When factoring: 22 LLtesting: p filesize runlength p~1,900,000 393,226 96k p~2,200,000 458,762 112k p~2,420,000 524,298 128k p~2,700,000 655,370 160k p~3,500,000 786,442 192k p~4,000,000 917,514 224k (none of the exponents in ranges above are available for checkout at the moment) p~5,000,000 1,048,586 256k p~5,500,000 1,310,730 320k (above here fits on a 1.44" floppy) p~7,000,000 1,572,874 384k p~8,000,000 1,835,018 448k p~10,000,000 2,097,162 512k p~11,000,000 2,621,450 640k p~14,000,000 3,145,738 768k p~16,000,000 3,670,026 896k p~20,000,000 4,194,314 1024k In general, size (2p) = size (p) * 2 -10 or filesize = runlength*4 + 10 Correct me if I've overgeneralized, George. Ken ------------------------------ From: Peter-Lawrence.Montgomery@cwi.nl Date: Wed, 27 May 1998 07:09:33 +0200 (MET DST) Subject: Mersenne: Suyama test and LL (was: Fermat base-3 for LL?) On 20 May 1998, Ernst Mayer wrote > Dear All: time to clear up this Fermat-base-3 business once and > for all (i.e. until the next wave of newbies start nattering about > it without bothering to look through this list's archives first.) (lines deleted) > Now, you may be asking why I bothered to write such a program if the > test is no faster than LL and moreover not definitive (at least regarding > primality - it WILL tell you for sure if the number is composite.) The > answer lies in the above program name. The base-3 test will not prove > primality of an M(p), but it can be used to quickly test the status of > any cofactor of an M(p) with one or more known factors. This is because > the Fermat-base-3 residue of an M(p) can be used (as with the Pe'pin > test, which is really just a Fermat-base-3 test of a Fermat number) > to perform a so-called Suyama posttest of the cofactor of the number > in question. The Suyama test is described in many references on NT, > (e.g. Riesel's book) so I'll not repeat the full description here. > > That is, the ONLY advantage of the Fermat-base-3 test is that it > yields a residue which, if the number proves composite, is still of > further use, unlike the LL residue, which is useful only for results > verification. The Suyama test can be used with the LL residue too. Read on. - --------- What is the Suyama test? The Suyama test assumes we have used a Fermat-like test to check a huge integer N for primality. We compute b^(N-1) mod N for some convenient base b coprime to N. using about log2(N) multiplications mod N. If b^(N-1) != 1 (mod N), we know N is composite. However we save the residue from b^(N-1). Later we find a factor f of N, and a cofactor N1 = N/f. Is N1 prime? If yes, then b^(N1-1) == 1 mod N1. From N = f*N1, we find b^(N-1) = b^(f*(N1-1) + (f-1)) == b^(f-1) mod N1. Typically f is small, perhaps 30 digits, and we can compute b^(f-1) mod N1 much faster than b^(N1-1) mod N1. We compare b^(f-1) mod N1 to [b^(N-1) mod N] mod N1. If these agree, we suspect N1 is prime. Otherwise it is composite. Example: N = 2^23 - 1 = 8388607 = 47*178481 3^(N-1) == 5884965 (mod N), so N is not prime With f = 47, N1 = 178481, we find 3^46 == 173573 (mod N1). Since 5884965 - 173573 = 5711392 = 32*N1, we suspect the cofactor N1 is prime. - ----------- Lucas-Lehmer test Let alpha = (sqrt(2) + sqrt(6))/2 and beta = (sqrt(2) - sqrt(6))/2. Then alpha*beta = -1 and alpha^2 + beta^2 = 4. Define L[n] = alpha^(2^n) + beta^(2^n) (n >= 1). Then L[1] = 4 and L[n+1] = L[n]^2 - 2 for n >= 1. Let q > 3 be prime. Then alpha^q (mod q) and beta^q (mod q) are closely related to alpha and beta: 2, 6 both quadratic residues mod q (q == +-1 mod 24): alpha^q == alpha beta^q == beta 2 a quadratic residue, 6 not (q == +-7 mod 24): alpha^q == beta beta^q == alpha 6 a quadratic residue, 2 not (q == +-5 mod 24) alpha^q == -beta beta^q == -alpha 2, 6 both quadratic non-residues (q == +-11 mod 24) alpha^q == -alpha beta^q == -beta When q = Mp and p >= 3 is odd, we know Mp == 7 (mod 24). If Mp is prime, then the second case applies, and alpha^(Mp+1) == alpha beta = -1 (mod Mp). Also beta^(Mp+1) == -1 (mod Mp). Hence L[p] = alpha^(2^p) + beta^(2^p) = alpha^(Mp+1) + beta^(Mp+1) == -2 (mod Mp) . Since L[p] = L[p-1]^2 - 2, we find L[p-1] == 0 (mod Mp) if Mp is prime. The converse is also true. This is the Lucas-Lehmer test. - ----------- LL variation of Suyama test Suppose we apply the Lucas-Lehmer test to Mp, and save L[p-1] mod Mp. Later we find a factor f of Mp. Is the cofactor N1 = Mp/f prime? Assume N1 is prime. 2 will always be a quadratic residue mod N1. Depending upon the (known) value N1 (mod 24), either alpha^(N1-1) == 1 (mod N1) and beta^(N1-1) == 1 (mod N1) or alpha^(N1+1) == beta^(N1+1) == -1 (mod N1). That is, alpha^(N-j) == beta^(N-j) == j (mod N1), where j is the Jacobi symbol 6 over j. We have saved L[p-1] and can compute L[p] == L[p-1]^2 - 2. However, L[p] = alpha^(Mp+1) + beta^(Mp+1) = alpha^(f*N1+1) + beta^(f*N1+1) == j^f * (alpha^(f*j+1) + beta*(f*j+1)) (mod N1) We can compute the right side in O(log(f)) multiplications mod N1, and compare it to L[p-1]^2 - 2. Example: p = 23, Mp = 8388607 = 47 * 178481. L[22] := 6107895 (mod Mp), so Mp is not prime. Let f = 47 and N1 = 178481. Then j = -1 since N1 == 17 (mod 24). We check that alpha^(-46) + beta^(-46) = beta^46 + alpha^46 == 2881 (mod N1), L[23] = L[22]^2 - 2 == 175600 (mod N1). These are negatives, so we suspect N1 is prime. - ---------------- Saving storage when testing cofactors of Mp As described above, to apply the Suyama test to a cofactor of Mp, we need to save the entire residue 3^(Mp - 1) mod Mp or L[p-1] mod Mp. If we need to save a 4000000-bit residue for each of the 65000 primes between 4 million and 5 million, the requisite storage space will exceed 30 gigabytes. Fortunately, it will usually suffice to save only 512 bits (say) of the L[p] (or 3^(Mp - 1)) residue. Specifically, suppose L[p] == 2^(p - 512)*saved + unsaved (mod Mp), where 0 <= saved < 2^512 and 0 <= unsaved < 2^(p - 512). That is, we save the most significant 512 bits of L[p]. Later, after we find a new cofactor N1 of Mp, we compute compare_to = j^f * (alpha^(f*j+1) + beta*(f*j+1)) (mod N1). Now we ask whether there exists a value of unsaved such that compare_to == 2^(p - 512)*saved + unsaved (mod N1) 0 <= unsaved < 2^(p - 512) The first line gives unsaved mod N1. We test whether this value falls within the bounds on the second line. Providing N1 is much larger than 2^(p - 512) (i.e., the product of the known factors of Mp is much smaller than 2^512, such as when we find two 30-digit factors by ECM), I anticipate few false positives. [If we _do_ get a positive result, it remains to prove primality. We can try a Fermat test on another base, but we don't know how to proceed if it passes all our tests.] ------------------------------ From: "Scott Kurowski" Date: Wed, 27 May 1998 01:21:16 -0700 Subject: Mersenne: RE: Mersenne Digest V1 #367 > From: George Woltman > Date: Mon, 25 May 1998 15:07:00 -0400 > Subject: Re: Mersenne: Locking out factoring assignments on v16.3.5 > > Hi Rick, > > At 09:21 AM 5/25/98 -0400, Rick Pali wrote: > >[Rick asked for LL tests only]...three exponents in the low six-million > range. I > >thought there was some mistake, but when I checked my individual report on > >PrimeNet, I saw that these were factoring tests. > > > >Have I set something wrong, is this a problem with 16.3.5 or has the locking > >out of factoring been disabled because we're venturing into new territory? > > The server is once again out of exponents below 5.26M to assign. > > That means version 15 users will get factoring assignments until they > upgrade to version 16. > > As to why you are seeing this problem in version 16, I do not have > an answer. Scott and I will figure it out. More than 1500 exponents > above 5.26M have been successfully assigned for LL testing to version > 16 clients, so I don't have any ideas right now. > > Regards, > George Problem solved. I forgot to apply the fix for the 16.3 HTTP NTPrime clients to the RPC NTPrime clients. Server 3.1.242 has the protocol change. I also fixed a problem checking in factor found results in the manual testing web form. regards scott ------------------------------ From: Morten Due Jorgensen Date: Wed, 27 May 1998 12:26:00 +0200 Subject: Mersenne: Double checking of factoring Newbie coming up! - so sorry, if this has been covered before. Of course the LL tests are double checked, but what about factoring results? A factor is naturally quite simple to verify, but is it done, and by whom? What about unfactored numbers, determined NOT to be prime by an LL test. Are these attempted factored later on? -or are _all_ the possibilites at hand to attempt factoring been used up, before a LL test is started? Regards, Morten Due Jorgensen Seven Technologies ------------------------------ From: Paul Leyland Date: Wed, 27 May 1998 03:41:07 -0700 Subject: RE: Mersenne: Double checking of factoring > Of course the LL tests are double checked, but what about factoring > results? A factor is naturally quite simple to verify, but is > it done, and > by whom? > > What about unfactored numbers, determined NOT to be prime by > an LL test. > Are these attempted factored later on? -or are _all_ the > possibilites at > hand to attempt factoring been used up, before a LL test is started? It depends. Factors for "small" exponents are certainly checked, and incompletely factored "small" numbers are later factored by various means. For me, "small" means that the exponent is less than 10,000. Other people go higher. My tables can be found at ftp://ftp.ox.ac.uk/pub/math/factors/mersenne and ftp://ftp.ox.ac.uk/pub/math/cunningham/2- Paul ------------------------------ From: JGrif91665@aol.com Date: Wed, 27 May 1998 07:51:28 EDT Subject: Mersenne: Restart Prime95 Is it normal for Prime95(ver 16.3) to contact the server every time after startup. James Griffin ------------------------------ From: Ken Kriesel Date: Wed, 27 May 1998 08:51:37 -0500 Subject: Re: Mersenne: Suyama test and LL (was: Fermat base-3 for LL?) At 07:09 AM 1998/05/27 +0200, Peter-Lawrence.Montgomery@cwi.nl wrote: ... >If we need to save a 4000000-bit residue for each of the 65000 >primes between 4 million and 5 million, the requisite >storage space will exceed 30 gigabytes. 30 gigabytes sounds like a lot but it does not all have to be online storage; at today's DAT tape prices it's only about $80 worth of tape. (Doing the full 2 - 20,500,000 however is rather pricy currently.) Ken ------------------------------ From: "Ernst W. Mayer" Date: Wed, 27 May 1998 13:56:19 -0400 Subject: Mersenne: Re: Error compiling lucas_mayer_V2.5.f90 on Sparc Sturle Sunde reports the following error message compiling lucas_mayer_V2.5.f90 on Sparc: >[sturles@hindarfjell]~/src $ uname -a >SunOS hindarfjell.ifi.uio.no 5.5.1 Generic_103640-17 sun4u sparc SUNW,Ultra-1 >[sturles@hindarfjell]~/src $ f90 -O3 -o lucas_mayer lucas_mayer_V2.5.f90 > > real(kind=r16),allocatable :: tmp16(:) > ^ >cf90-130 f90comp: ERROR LUCAS_DISTRIB, File = lucas_mayer_V2.5.f90, Line = >233, Column = 12 > The kind type parameter value -1 is not valid for type REAL. The above line (and a similar one in the header of the fft_square subroutine) should read real(kind=max(r8,r16)),allocatable :: tmp16(:) Explanation: at compile time the code obtains F90 kind type parameter values for 8-byte reals (via r8=selected_real_kind(15,30), which asks for a real data type that gives at least 15 decimal digits of accuracy and allows decimal exponents having a range of at least [-30,+30]) and also checks whether an extended-precision real data type (via r16=selected_real_kind(18,50)) is available. Note that even though the variable name "r16" seems to imply a 16-byte real, the kind type parameter pair which the code specifies, (18,50), allows any real data type giving at least 18 decimal digits of accuracy and with decimal exponents having a range of at least [-50,+50] to serve as an extended- precision real type for initializations. In F90, if a kind type value comes back negative, that means that the requested type is not available. In this case, the proper thing is to make sure the code then defaults to one of the guaranteed-available types, in this case r8. I had used kind=max(r8,r16) in the typedef of other similar variables, but neglected to propagate it to the rest of the code. I didn't spot the error since the two systems I compiled on (Alpha and SGI) both support extended-precision reals, i.e. would return a positive (and > r8) value for r16. SPARC users can either change the 2 culprit statements manually, or download the revised source code from my ftp site: ftp://nigel.mae.cwru.edu/pub/mayer/lucas_mayer_V2.5.f90.gz - -Ernst ------------------------------ From: "Michiel van Loon" Date: Wed, 27 May 1998 22:52:10 +0200 Subject: Mersenne: PRIMEOS2 now also supports 64 bit factoring Hi all OS/2 users, As could be expected, it was a trivial error in the port from Linux to OS/2 which caused the 64 bit factoring code to fail, which forced me to bring out the intermediate version 3..0. But I am happy to announce the release of PRIMEOS2 v3.1.2 the full OS/2 port of MPRIME 16.3.2, which includes 64 bit factoring, and LL tests upto 1024 K FFT's. Also a porting bug in the 62 bit factoring code, which made it to alway fail to find a factor has been removed. As usual the software can be found at: http://www.xs4all.nl/~mfvl/prime Best regards, Michiel van Loon ------------------------------ From: Saint D Date: Wed, 27 May 1998 21:05:27 -0400 Subject: Mersenne: Manually reserving ranges Just a quick question. I'm one of those dinosaurs running Prime95 v14.4.1 on 5 computers, only one of which with 'Net access. I checked out the manual exponent reservation Web form system at entropia.com, but it says that the Web form system is only for those running v15.4 or later. Does this mean that George is going to continue to be stuck responding to my (and surely others) email requests for ranges and such? Thanks, Kel ------------------------------ End of Mersenne Digest V1 #368 ******************************