Mersenne Digest Thursday, 30 April 1998 Volume 01 : Number 353 ---------------------------------------------------------------------- From: Nick Craig-Wood Date: Tue, 28 Apr 1998 10:22:55 +0100 (BST) Subject: Re: Mersenne: Another test other than Lucas-Lehmer In on Mon 27 Apr, Charles F. Kerchner III wrote: > 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; > } Its probably quicker to calculate 3^(2^(n-1)) and check for the result being +/-3 at the end x = 3; for (i = 0; i < p; i++) { x = (x * x) mod Mn; } if (x == 3 || x == p - 3) { /* its a probable prime... */ } I tried this test on the n=1...1000 and it was 100% accurate. I can't see a way of making this significantly faster than the LL test though! - -- Nick Craig-Wood ncw1@axis.demon.co.uk http://www.axis.demon.co.uk/ ------------------------------ From: "Charles F. Kerchner III" Date: Tue, 28 Apr 1998 09:03:39 -0400 Subject: Re: Mersenne: Another test other than Lucas-Lehmer > I tried this test on the n=1...1000 and it was 100% accurate. > > I can't see a way of making this significantly faster than the LL test > though! > The reason we're working on Mersenne primes is that the LL test, which is > deterministic, is just as fast as most pseudoprime tests - certainly it's > just as fast as either of the tests you discussed in your post. > > We're testing N in time about log N ^2 loglog N; it's hard to imagine how to > > do it much faster. My point was to bring to people's attention the fact that there are other tests besides the Lucas Lehmer (LL) test that are "100% accurate" and report "probable prime" status, at least. The LL test requires p-2 steps for Mersenne primes of Mp = 2^p-1 and is deterministic. The LL test is always going to take p-2 steps. There is no way to reduce this number. The number of steps the test that I described requires is proportional to the size of the number we are testing (for Mersenne primes Mp = 2^p - 1, the portion of the number we are testing requires p-2 steps). It might be possible to reduce the number of steps (i.e. by testing a smaller portion of the number) for a non-determinstic test that reports the "probable prime" status. I WASN'T asking if my test was faster or slower than the LL test. I was asking people "to imagine hard how to do it much faster". There may be ways to simplify this tests with a combination of other "probable prime status" tests (i.e. n-1 and n+1 primality tests) so that the time or number of steps to drastically reduced (if we could test Mp in p/2 steps to see if it were a "probable prime" and each step requires about the same time as one of the LL steps, I think this would be great). All I want is to stir up people's "mathematical imaginations". Chip Kerchner ------------------------------ From: George Woltman Date: Tue, 28 Apr 1998 09:07:16 -0400 Subject: Re: Mersenne: Rolling Average At 09:38 PM 4/27/98 -0700, John R Pierce wrote: >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?) Yes, RollingAverage=1235 means your machine is 23.5% faster than expected. However, the expected value is merely an extrapolation based on my own PPro 200 (the fastest machine I own) with the old Orion chip set. Regards, George ------------------------------ From: "Harijs Ausmanis" Date: Tue, 28 Apr 1998 22:05:17 +0300 Subject: Re: Mersenne: Squeeky P60!!! This is a multi-part message in MIME format. - ------=_NextPart_000_0015_01BD72F1.BA6C81C0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Exactly the same happens on my Cyrix - the client sometimes starts = accessing the hard drive every second. With the System Monitor I have = determined that the exact amount of information is being read or written = to the hard drive every second, it was something like either 170 or 250 = bytes. When I stop the client, the hard drive, judging by the noise, = "deletes" everything that was written on it in those 170 byte portions, = however, the System Monitor again shows information being written or = deleted in the same amounts, of course, those amounts are now measurable = in kilobytes. I experience exactly the same symptoms as with the Prime95 client, so = with Distributed.net GUI clients (only the GUI, the CLI and DOS mode = clients don't cause this) and with the PiHex client. I have yet only = reported this problem to the PiHex coordinator, and he has promissed me = to correct this bug if we succeed to discover what exactly is going on. = Currently I am trying to get a program that shows to exactly which file = on the hard drive something is being written (Colin Percival's - PiHex = coordinator's - guess is that Windows is swapping the GUI to the swap = file on the hard drive, for some reason) and a friend has promissed to = get such a program tomorrow. The only differences are that in my case the client(s) are not being = slowed down by this writing to the hard drive, and that a reboot isn't = needed, a simple stopping of any of those clients helps. I have a Gateway P100 that occasionally will get into a pattern of hard = drive activity during an LL test where it seems to access the drive about once = every two seconds. Kinda like a chirp, but it is not the speaker, it's the = harddrive.=20 This will happen randomly, and the iteration times will slow down = byabout 10%=20 when it happens. The only thing that will stop it is a reboot. _______________________________________________ _________| = |_________ \ | 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_0015_01BD72F1.BA6C81C0 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable
Exactly the same happens on my Cyrix - the client = sometimes=20 starts accessing the hard drive every second. With the System Monitor I = have=20 determined that the exact amount of information is being read or written = to the=20 hard drive every second, it was something like either 170 or 250 bytes. = When I=20 stop the client, the hard drive, judging by the noise, = "deletes"=20 everything that was written on it in those 170 byte portions, however, = the=20 System Monitor again shows information being written or deleted in the = same=20 amounts, of course, those amounts are now measurable in = kilobytes.
I experience exactly the same symptoms as with the = Prime95=20 client, so with Distributed.net GUI clients (only the GUI, the CLI and = DOS mode=20 clients don't cause this) and with the PiHex client. I have yet only = reported=20 this problem to the PiHex coordinator, and he has promissed me to = correct this=20 bug if we succeed to discover what exactly is going on. Currently I am = trying to=20 get a program that shows to exactly which file on the hard drive = something is=20 being written (Colin Percival's - PiHex coordinator's - guess is that = Windows is=20 swapping the GUI to the swap file on the hard drive, for some reason) = and a=20 friend has promissed to get such a program tomorrow.
The only differences are that in my case the = client(s) are not=20 being slowed down by this writing to the hard drive, and that a reboot = isn't=20 needed, a simple stopping of any of those clients helps.
 
<!--StartFragment-->
I have a Gateway P100 that = occasionally will=20 get into a pattern of hard drive
activity during an LL test where it = seems to=20 access the drive about once every
two seconds.  Kinda like a = chirp, but=20 it is not the speaker, it's the harddrive.
 This will happen = randomly,=20 and the iteration times will slow down byabout 10%
when it = happens. =20 The only thing that will stop it is a reboot.
          &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_0015_01BD72F1.BA6C81C0-- ------------------------------ From: STL137 Date: Tue, 28 Apr 1998 20:17:53 EDT Subject: Mersenne: Red and Alexa Is there a reason the last Mersenne Digest had a red background? Uggghhh. OR is it AOL quirk? Next: I believe this archive thingy is called alexa. I'll go check or something. STL137 ------------------------------ From: Joel Smith Date: Tue, 28 Apr 1998 21:46:41 -0700 Subject: Mersenne: Prime numbers Here are a couple of emails I received from a lady in Germany. She has some general philosophical questions about prime numbers that I made some attempts to answer, but I think the GIMPS group will have some thoughts. I suggested that she post to GIMPS but she had some problems doing this, so I am forwarding her email here. You can reply either to GIMPS or directly to Susanne (schulzsu@rz.uni-potsdam.de). Thanks! Joel Smith ___________________________________________________________ Date: Tue, 17 Mar 1998 18:42:31 +0100 (MET) From: Susanne Schulz To: joel@netgate.net Subject: prime numbers Dear Joel, I'm a film student from Germany and currently I am doing some research for a novel which deals with some aspects of physics concerning the philosophical side of natural sciences in general and prime numbers in particular, and probably even their impact on every-day-life. So far I have only come across a lot of "you-must-be-a-complete-math-crack-to-understand-this"-pages, which did not make me wiser in any way. I'm a complete math-loser anyway, I don't even get the 2 by n minus one thing, therefore it is completely impossible to explain anything to me by using numbers instead of words. My question is: What is so special about prime numbers? What is their mystery? I'm not talking about the fact, that their only divisors are 1 and themselves. I'm interested in the philosophical impact on prime numbers. In his book 'contact' Carl Sagan e.g. wrote, that the aliens would use prime numbers to get in contact with planet earth because their origin could not only be not natural, but would also require a certain level of intelligence to either send or detect them. During my surfing sessions I also came across some articles which dealt with the connection between prime numbers and nucleotid bases, and I would also be very interested in that subject, too. Any hints would be great, Thanks for Your efforts, Susanne Schulz ___________________________________________________________ Date sent: Thu, 26 Mar 1998 17:56:31 +0100 (MET) From: Susanne Schulz To: joel@u1.netgate.net Subject: Re: prime numbers Dear Joel, thank You very much for answering my e-mail, it sure helped! I just signed up for the mailing list and my next e-mail will be going there. Concerning Your statements towards prime numbers, a few more questions have evolved. Since I really appreciated Your way of describing and explaining things (comparing the search for primes with the search for gold e.g.) it would be nice if You could answer them, too. 1. If primes are the foundation of all integers, are they the foundation of all (numeric) logic, too? Without primes, were we more limited? Or is a world without primes completely beyond imagination? 2. If primes are getting harder to find (the bigger they get?), could there be a final prime? And is there a connection between this question and the aspect of physics dealing with endless time and space? 3. Is there a scheme to be found in the spaces between one prime number and their follow-up? If the spaces get bigger, is that happening on a regular basis? 4. Talking about Cryptology: in Carl Sagan's novel 'contact' it is said, that prime numbers are something very artificial, something that a galaxy, or a pulsar, e.g. could not send. Well, I hope I don't get too far in this case, but IF prime numbers are artificial, what does that indicate? Artificialty must be created, so does their mere existance indicate a creator? 5. Do You know anything about Twin Primes? Did anyone come up with a theory so far? Thanks for Your time and Your efforts, take care, Susanne Schulz ------------------------------ From: kotera@asahi.email.ne.jp (Kotera Hiroshi) Date: Wed, 29 Apr 1998 14:02:31 +0900 Subject: Mersenne: 1 is prime? Dear all Many students in high school ask me 1 and 2 is prime number. Answer please. ++++++++++++++++++++++++++++++++++++++++++++ Hiroshi Kotera 1014-4 Tokujyo-cho Nara City 630-8144 JAPAN email : kotera@asahi.email.ne.jp http://www.asahi-net.or.jp/~nj7h-ktr/ ++++++++++++++++++++++++++++++++++++++++++++ ------------------------------ From: "Cornelius Caesar" Date: Wed, 29 Apr 98 11:30:20 CES Subject: Re: Mersenne: 1 is prime? Kotera Hiroshi wrote: >Many students in high school ask me 1 and 2 is prime number. 2 is the smallest prime number. Although 1 also matches the definition (divisible only by 1 and itself) it is not regarded as prime because then a prime factorization would not be unambiguous. Cornelius Caesar ------------------------------ From: Chris Caldwell Date: Wed, 29 Apr 1998 06:55:46 -0500 (CDT) Subject: Re: Mersenne: 1 is prime? On Wed, 29 Apr 1998, Kotera Hiroshi wrote: > Many students in high school ask me 1 and 2 is prime number. > Answer please. I give a long answer on http://www.utm.edu/research/primes/notes/faq/one.html but the short answer is one is more special than a prime, it is a unit (not a prime). And yes, two is definately prime. There have been times that one was considered prime by some researchers, but now the full mass of modern mathematics has weighed in, and to appropriately separate the elements in number rings we need to be careful how we define unit (divisors of unity), irreducible and prime. See also http://www.utm.edu/research/primes/glossary/Prime.html Chris (caldwell@utm.edu) ------------------------------ From: Jean-Luc Cooke Date: Wed, 29 Apr 1998 11:22:24 -0400 Subject: Re: Mersenne: 1 is prime? This is a multi-part message in MIME format. - --------------F20B12FD8D9C587F5FE38A40 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit A prime number is defined as any number that is evenly divisible by one and it's self. So by definition, 1 cannot be prime because it's divisible by one or itself. The number 2 is prime for the same reason, but the numbers [one, itself] are different. That's about as simple as it can be made. I sure there is more elaborate reason, but that's the essence of it all. TTYL Jean-Luc Cooke, Nepean (Ottawa) Canada. Kotera Hiroshi wrote: > Dear all > Many students in high school ask me 1 and 2 is prime number. > Answer please. > ++++++++++++++++++++++++++++++++++++++++++++ > Hiroshi Kotera > 1014-4 Tokujyo-cho > Nara City 630-8144 JAPAN > email : kotera@asahi.email.ne.jp > http://www.asahi-net.or.jp/~nj7h-ktr/ > ++++++++++++++++++++++++++++++++++++++++++++ - -- Jean-Luc Cooke Carleton University, Electrical Engineering There is a 90% chance that right at this moment I am doing Calculus. God damn Newton, damn him to hell! - ---------------------------------------------------------------------- AOL-IM ID: JLinOTTAWA Get one: register.netscape.oscar.aol.com - ---------------------------------------------------------------------- ICQ# 4474419 Get it: www.mirabilis.com - ---------------------------------------------------------------------- Email addresses jlcooke@ottawa.com jlcooke@magma.ca jlcooke@magmacom.com jlcooke@engsoc.carleton.ca jlcooke@chat.carleton.ca - ---------------------------------------------------------------------- - --------------F20B12FD8D9C587F5FE38A40 Content-Type: text/x-vcard; charset=us-ascii; name="vcard.vcf" Content-Transfer-Encoding: 7bit Content-Description: Card for Jean-Luc Cooke Content-Disposition: attachment; filename="vcard.vcf" begin: vcard fn: Jean-Luc Cooke n: Cooke;Jean-Luc org: Carleton University adr: 270A Dalehurst Dr.;;;Nepean;ON;K2G 4M8;Canada email;internet: jlcooke@ottawa.com title: Electrical Engineering Student tel;work: na tel;fax: na tel;home: na note: My web page address is: www.engsoc.carleton.ca/~jlcooke/ x-mozilla-cpt: ;0 x-mozilla-html: TRUE version: 2.1 end: vcard - --------------F20B12FD8D9C587F5FE38A40-- ------------------------------ From: David L Nicol Date: Wed, 29 Apr 1998 14:47:28 -0500 Subject: Mersenne: FFT is worst case use of demand-paged virtual memory Harijs Ausmanis wrote: > I have a Gateway P100 that occasionally will get into a pattern of > hard drive > activity during an LL test where it seems to access the drive about > once every > two seconds. Kinda like a chirp, but it is not the speaker, it's the > harddrive. > This will happen randomly, and the iteration times will slow down > byabout 10% > when it happens. The only thing that will stop it is a reboot. That sounds like virtual memory thrashing. Speaking as a Gateway tech support ophone guy (yes I was, for several months, my employee ID was 7294) I'd suggest playing with your virtual memory settings. Or stopping processes until the problem goes away. Monitoring the available memory and virtual memory. You didn't say which OS you are using but assuming you are using windows 95 it comes with a quite nice suite of system monitoring tools although I'm not sure how to install them. The real reason I'm responding to this is not to give questionable PC configuration advice but to review the paper found at http://www.cs.dartmouth.edu/~nicol/papers/fft.ps which is by David M. Nicol, the professor at Dartmouth who is no relation to myself. I am and have been David L. Nicol the programmer in Kansas City but I welcome confusion with such an outstanding individual. In "Performing Out-of-Core FFTs on parallel Disk Systems" Drs Cormen and Nicol present a method for optimising performance of large FFTs. First they explain why the FFT is a worst-case use of on-demand-paged virtual memory: All the points in a large data set must be hit several times during the process, even when the recursion has been completely unrolled. The then present a solution, which is to know which parts of the intermediate data are going to be required next and getting them ahead of time, explicitly, rather than relying on the OS-provided virtual memory. Since large FFTs _ARE_ computation-bound, having a thread that pre-fetches the pages the computation is going to need completely eliminates slowdown due to IO waits. This isn't a problem (except, apparently, for Harijs Ausmanis) as the GIMPS project still deals with FFTs small enough to be handled entirely within the computer's memory. The LL test running on this workstation is using slightly (according to the "top" utility) less than 3M or memory, and I have it set to shut itself off for five minutes whenever the load goes above 2 processes waiting, so I never see it swap out. But looking ahead to when we are trying to LL-test numbers too large to hold "in core" it might make sense to investigate out-of-core FFT algorithms. On a machine that uses fully buffered file I-O, writing intermediate data to a "file" will not slow down the computation much, as intermediate data small enough to get held in the buffer will stay there until the temporary file would be overwritten. The effect of switching to a out-of-core algorithm would be to exchange allocated memory for IO-buffer memory, and to smooth the transition to paging when memory does run out, as instead of using ad-hoc demand paging, an organized read on the file (which will be getting kept, as much as necessary, on disk at that point) will be done instead. And more data will be getting written to disk, as intermediate files in addition to the p and q files will be saved during OS syncs. Hell, for all I know George's FFTs are already doing something like this and the p and q files aren't just checkpoints in case of crash but are an integral part of an out-of-core FFT algorithm that has been running here all along. I'm a computer programmer, not a mathematician. David L. Nicol (not the author of the paper, who was not consulted prior to writing this e-mail) ______________________________________________________________________ David Nicol 816.235.1187 UMKC Network Operations david@news.umkc.edu "Lights off. Good." --Koko ------------------------------ From: "John R Pierce" Date: Mon, 29 Jun 1998 20:15:19 -0700 Subject: Re: Mersenne: FFT is worst case use of demand-paged virtual memory >This isn't a problem (except, apparently, for Harijs Ausmanis) as >the GIMPS project still deals with FFTs small enough to be handled >entirely within the computer's memory. The LL test running >on this workstation is using slightly (according to the "top" utility) >less than 3M or memory, and I have it set to shut itself off for five >minutes whenever the load goes above 2 processes waiting, so I never >see it swap out. But looking ahead to when we are trying to LL-test >numbers too large to hold "in core" it might make sense to investigate >out-of-core FFT algorithms. Ah, but at least on our 512k cache pentiums, it IS thrashing the cache some. But I believe that George has already optimized the assembler language version to prefetch cache lines and minimize level-1 misses. re: the thrashing previously mentioned. One of my systems used to do that. I forget what I finally decided caused it. Generally it would stop after 10 or 15 minutes. If I remember, defragging my D: drive then setting the swapfile to a healthy minimum size on D: pretty much stopped it. - -jrp ------------------------------ From: "Terry S. Arnold" Date: Thu, 30 Apr 1998 00:17:12 -0700 Subject: Re: Mersenne: Another test other than Lucas-Lehmer The problem with the Miller-Rabin test is that it is has a probability of declaring a composite number a strong pseudo prime of <1/4, although I have seen tighter bounds in Menzies, Vanstone & van Oorshitt's cryptography book. The LL test gives a proof of primality with an error probability of 0. If the cost is nearly the same then the LL test is clearly the better choice. Since we are on this sort of tack, has any one taken a look at using the Fermat test? It may be an alternative to factoring as a method for determining whether a number is worth spending the time of LL testing. Terry Terry S. Arnold 2975 B Street San Diego, CA 92102 USA tarnold@computer.org (619) 235-8181 (voice) (619) 235-0016 (fax) ------------------------------ End of Mersenne Digest V1 #353 ******************************