Mersenne Digest Wednesday, November 7 2001 Volume 01 : Number 902 ---------------------------------------------------------------------- Date: Mon, 5 Nov 2001 17:22:30 -0800 From: "Stephan T. Lavavej" Subject: Mersenne: Mersenne Statistics Hi, It's nice to see some people still remember my work with the statistical distribution of Mersenne primes. :-> If anyone is interested, I have the paper I wrote on the subject up at: http://stl.caltech.edu/paper.html You can link to it freely. To summarize: Let M(x) be the number of primes P <= x for which 2^P - 1 is prime. I believe: M(x) ~= e^gamma log[2](x) - 2 ^ (1/e^gamma) Using data up to and including the 37th Mersenne, I predicted: 38: 4,699,385 39: 6,935,171 (hence the "missing Mersenne") 40: 10,234,658 41: 15,103,913 42: 22,289,772 43: 32,894,385 44: 48,544,264 45: 71,639,751 50: 501,458,270 55: 3,510,067,986 60: 24,569,496,568 65: 171,979,620,925 I don't believe in the existence of a missing Mersenne anymore, but I do agree we should be finding one soon - that is, if there are any left! Heh. Stephan T. Lavavej _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 6 Nov 2001 09:54:07 -0000 From: "Stuart Kennedy" Subject: Mersenne: RE: L-L algorithm Thought this might be interesting and maybe useful. Fermat's theorem (i.e. a^M(p) mod M(p) = a) can be used to prove Mersenne primes as long as 'a' isn't a power of 2 . ... so the algorithm is very similar to L-L only you can get rid of the -2 and you will end up with:- M(p) is prime if s:=a^2 after p iterations where 'a' isn't a power of 2 and is the initial condition for s (usually 4 in L-L). I realise that there aren't many clock cycles used to take away 2, even 10,000,000 times. But I think it makes the algorithm nice and neat and it's easy to see why it works for primality proof. Stuart Kennedy _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 6 Nov 2001 13:41:45 +0100 (MET) From: Wojciech Florek Subject: Mersenne: Re: Mersenne Digest V1 #901 Hi all! I've removed MD #901 and I don't remeber a subject of the thread, but there was discussion on the Mersenne prime distribution. The Nole islands theory has been recalled very often in this list, so I'm not going to go into details. About a year ago I looked at known primes and---as many of you---noticed that they went in pairs. If I remember well I even posted a message on it... It seems that exponents of the Mersenne primes are located near some powers of two. In most cases (say about 70%) if M(p) is prime than p=3*2^n+q OR p=3*2^n-q, where q is prime. Only in 11 cases q is composite (in both cases, i.e. for p=2^n+q AND 2^n-q). However, prime q is over-represented for small Mersennes. Including p=44497=3*8192+19921=3*16384-4655 eight Mersenne primes have composite q. Nevertheless the Mersenne primes "group" near M(2^{3*2^n}). This "theory" predicts a Mersenne prime near 4500000, since there should be a prime M(p) for p>3145728 and p<6291456, where is a gap! (Remember the ver 17 bug!). I think that there is another pattern, which "excludes" some possible candidates, since a similar gap is for 1923*2^21=6291456. It is possible that this prime has a twin-brother (sister?) very near or the next should be found for 12,582,912 Subject: Re: Mersenne: number of processors participating "Terry S. Arnold" wrote: > > .... > > Another consideration is that many system/network administrators have > gotten ludicrous about what they will allow on their networks. They think > that Prime95 just might let in a virus or even worse spill "company > secrets".... In a recent ethics briefing I was told that running seti@home on work PC's was a no-no because there had been three break-ins to computers using that program as a back door. No idea whether that is really the case, and no idea what communication scheme seti@home uses. Anyone familiar with this perceived problem? Gerry - -- mailto:gerrysnyder@mediaone.net _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 7 Nov 2001 15:59:00 +0100 From: "Steinar H. Gunderson" Subject: Mersenne: Re: SMT On Mon, Nov 05, 2001 at 07:33:21PM -0000, bjb@bbhvig.uklinux.net wrote: >_If_ SMT appears to the OS to be SMP (which I thought was the >point - SMT is effectively a cheap way of mounting two processors >in one package), then surely the user will have to run two >processes. There is no design problem; at present a user with a >dual-processor system can elect to run LL testing on one >processor & trial factoring on the other - or LL testing on both, if he >wishes. But if SMT appears to the OS to be SMP, we have another quite big problem: The good old mantra of "Prime95 doesn't make your system run slower" won't be valid anymore (even if you have enough RAM). Imagine the following (quite likely) scenario: Some process (be it a game, a rendering, MP3 encoding or virtually anything) wants as much CPU power as possible, and runs at normal priority. At the same time, the GIMPS software (mprime/Prime95/ntprime/etc.) also wants as much CPU-power as possible, but it runs at idle priority. The OS puts the first process on one of the "processors" -- but the second "processor" is still free, and the OS puts the GIMPS process there. But there's still only one CPU - -- and even if the Intel claim of 30% total performance increase is true, each of those CPUs only work at about 65% of a normal CPU. In other words -- at the processor level, the GIMPS process is given exactly the same priority as the other process, even though the OS has another idea of priorities. Conclusion: Prime95 will make any CPU-hungry program _at least_ 35% slower on an SMT system. Am I missing something here? Can we hope that sensible operating systems simply don't schedule an idle thread on a "CPU" if the other "CPU" is busy doing normal-priority tasks (in the SMT case only , of course)? Can some priority system on the processor level be implemented (and even more important, be _supported_ in the OSes as well)? Or are we simply required to advise people not to run Prime95 on SMT-enabled systems unless you want to make your machine run at two thirds the normal maximum speed? /* Steinar */ - -- Homepage: http://www.sesse.net/ _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 7 Nov 2001 23:38:28 -0000 From: bjb@bbhvig.uklinux.net Subject: Re: Mersenne: Re: SMT On 7 Nov 2001, at 15:59, Steinar H. Gunderson wrote: > But if SMT appears to the OS to be SMP, ... therefore neither the OS nor the application needs to understand the distinction ... > we have another quite big > problem: The good old mantra of "Prime95 doesn't make your system run > slower" won't be valid anymore (even if you have enough RAM). Imagine > the following (quite likely) scenario: > > Some process (be it a game, a rendering, MP3 encoding or virtually > anything) wants as much CPU power as possible, and runs at normal > priority. At the same time, the GIMPS software > (mprime/Prime95/ntprime/etc.) also wants as much CPU-power as > possible, but it runs at idle priority. Yep; also applies to existing SMP systems. > The OS puts the first process > on one of the "processors" -- but the second "processor" is still > free, and the OS puts the GIMPS process there. But there's still only > one CPU -- and even if the Intel claim of 30% total performance > increase is true, Where does this figure come from? Sounds very low to me. Dual- processor SMP systems tend to have a total throughput around 1.9x a system containing a single processor of the same type & running at the same speed, though this does depend on memory loading. Is the 30% a figure for the expected increase in performance of a "typical" application if a suitable compiler can identify segments which can be run in parallel on a SMT system? > each of those CPUs only work at about 65% of a > normal CPU. In other words -- at the processor level, the GIMPS > process is given exactly the same priority as the other process, even > though the OS has another idea of priorities. Conclusion: Prime95 will > make any CPU-hungry program _at least_ 35% slower on an SMT system. > > Am I missing something here? Can we hope that sensible operating > systems simply don't schedule an idle thread on a "CPU" if the other > "CPU" is busy doing normal-priority tasks (in the SMT case only , of > course)? linux _tries_ to run a thread on the same CPU it used last time, in order to keep the cache contents. However, after a few other processes have "had a go" at that CPU, the cache will be well clobbered, so it will then run on any processor. Windows SMP can optionally tie a thread to a single CPU, in which case it will not execute on any other CPU. Even if it has to wait forever to get at the designated CPU. However, most threads will run on any available CPU. Normally it works like a single queue with multiple servers. Both systems seem to work reasonably well. Theoretically the linux model is better, but in practice, differences seem to be quite small, and are more likely due to the fact that the linux scheduler can execute about twice as many task switches per second as Windows can due to more efficient code. Even on uniprocessor systems. > Can some priority system on the processor level be > implemented (and even more important, be _supported_ in the OSes as > well)? Or are we simply required to advise people not to run Prime95 > on SMT-enabled systems unless you want to make your machine run at two > thirds the normal maximum speed? Hopefully the situation will not arise, for the reasons I've indicated above. Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 7 Nov 2001 23:38:28 -0000 From: bjb@bbhvig.uklinux.net Subject: Re: Mersenne: Re: Mersenne Digest V1 #901 On 6 Nov 2001, at 13:41, Wojciech Florek wrote: > I've removed MD #901 and I don't remeber a subject of the thread, but > there was discussion on the Mersenne prime distribution. The Nole > islands theory has been recalled very often in this list, so I'm not > going to go into details. > > [ ... big snip ...] > > To finish, I do not think that distrubution of prime Mersenne numbers > is random, but our "sample" (38 instances) is too small. Umm - let's shift into ultra-precise terminology mode ... The distribution of Mersenne primes is _by definition_ NOT random. _NO_ actual distribution can possibly be random! We sometimes (often) use the term "random distribution" slackly to mean "a distribution which passes all known tests for randomness". As you point out, 38 data points is a very small sample. It is quite possible that the distribution is _truly_ non-random yet with our limited data we still cannot distinguish it using statistical tests. Neither is there sufficient data to give much weight to the Noll Island hypothesis. There are as many instances of "singletons" as there are of really obvious pairs. Mind you, very large samples are not always helpful either. The sequence of digits in the decimal expansion of pi are also _by definition_ non-random; we know the decimal expansion to many billions of digits, yet the statistical tests for randomness still fail to distinguish the sequence from a theoretical truly non-random one. Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 7 Nov 2001 23:38:28 -0000 From: bjb@bbhvig.uklinux.net Subject: Re: Mersenne: number of processors participating On 6 Nov 2001, at 16:09, Gerry Snyder wrote: > > Another consideration is that many system/network administrators > > have gotten ludicrous about what they will allow on their networks. > > They think that Prime95 just might let in a virus or even worse > > spill "company secrets".... > > In a recent ethics briefing I was told that running seti@home on work > PC's was a no-no because there had been three break-ins to computers > using that program as a back door. Given the number of systems running seti@home, that sounds pretty secure. As a comparison, about 10% of systems running Microsoft IIS were compromised by either Code Red or Nimda. > > No idea whether that is really the case, and no idea what > communication scheme seti@home uses. Anyone familiar with this > perceived problem? No, I don't know exactly what seti@home does. Prime95, NTPrime & mprime runs no communications listener; when it wants to communicate with PrimeNet _it_ initiates the connection. The only way anyone could possibly crash into a system because it is running Prime95 (or NTPrime, or mprime) is to detect an active connection to the PrimeNet server and to forge messages coming from the server. _If_ this was practical (it shouldn't be, for several reasons involving randomised IP sequence numbers, TCP windowing etc.) then the forged message would still have to be carefully crafted _and_ exploit a buffer overflow somewhere in the communications handlers on your system. { Note that there have been over the last couple of years patches for most operating systems (certainly Win 95, 98, NT, most variants of linux) which corrected problems relating to the "randomised" sequence numbers being too easy to guess. If you're moderately to severely paranoid about the security of your computer system, you should make sure you have these patches installed. Note that Windows has a nasty habit of uninstalling patches relating to networking if you change the configuration in any way :( } Now I'm not stating that it might not be possible to demonstrate a break in to a communications stream in a laboratory situation, but in the real world there are so many "ifs and buts" about the procedure that it would hardly be worthwhile. Note in particular that, if Prime95 can be crashed into in this way, then so can any program on the system which uses TCP connections. Prime95 itself (and NTPrime, and mprime) have been coded in such a way that there appears to be no risk of a buffer overflow exploit caused by the application itself. Critical data passed between Prime95 client & PrimeNet server are also protected by non-standard embedded checksums, so the integrity of the data appears to be pretty secure, too. Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 07 Nov 2001 19:28:38 -0500 From: Nathan Russell Subject: Re: Mersenne: number of processors participating At 11:38 PM 11/7/2001 +0000, Brian Beesley wrote: >Prime95, NTPrime & mprime runs no communications listener; >when it wants to communicate with PrimeNet _it_ initiates the >connection. The only way anyone could possibly crash into a >system because it is running Prime95 (or NTPrime, or mprime) is >to detect an active connection to the PrimeNet server and to forge >messages coming from the server. Note also that the GIMPS clients produce ~6-7 orders of magnitude less traffic than a web browser (which carries out very complicated operations in turning its raw data into graphics on the screen) in a given number of days. The numbers are equally favorable when compared with email clients, newsreaders and even instant messaging programs. Nathan _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 07 Nov 2001 20:13:43 -0500 From: Nathan Russell Subject: Re: Mersenne: number of processors participating At 07:28 PM 11/7/2001 -0500, Nathan Russell wrote: >At 11:38 PM 11/7/2001 +0000, Brian Beesley wrote: > >>Prime95, NTPrime & mprime runs no communications listener; >>when it wants to communicate with PrimeNet _it_ initiates the >>connection. The only way anyone could possibly crash into a >>system because it is running Prime95 (or NTPrime, or mprime) is >>to detect an active connection to the PrimeNet server and to forge >>messages coming from the server. > >Note also that the GIMPS clients produce ~6-7 orders of magnitude less >traffic than a web browser (which carries out very complicated operations >in turning its raw data into graphics on the screen) in a given number of days. > >The numbers are equally favorable when compared with email clients, >newsreaders and even instant messaging programs. That should be 'highly, but not equally, favorable - sorry. >Nathan > >_________________________________________________________________________ >Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm >Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers > _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 07 Nov 2001 22:30:50 -0500 From: George Woltman Subject: Re: Mersenne: Re: SMT At 11:38 PM 11/7/2001 +0000, bjb@bbhvig.uklinux.net wrote: > > The OS puts the first process > > on one of the "processors" -- but the second "processor" is still > > free, and the OS puts the GIMPS process there. But there's still only > > one CPU -- and even if the Intel claim of 30% total performance > > increase is true, > >Where does this figure come from? Sounds very low to me. Dual- >processor SMP systems tend to have a total throughput around >1.9x a system containing a single processor of the same type & >running at the same speed, though this does depend on memory >loading. I agree with Steinar's intriguing observation. Intel's SMT looks like two CPUs to the operating system but the two CPUs share one core. The 1.3x number comes from Intel's white papers. They report two threads operating on one CPU core increases throughput by up to 30%. So, Steinar's rough calculation that prime95 and the user's foreground task would both operate at 65% efficiency seems accurate - unless there is some kind of OS change made. I think Brian's comments apply to SMP systems where prime95 will only really have an impact if the other task is also heavily competing for the memory bandwidth. _________________________________________________________________________ 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 #902 ******************************