Mersenne Digest Wednesday, December 10 2003 Volume 01 : Number 1096
---------------------------------------------------------------------- Date: Fri, 5 Dec 2003 20:25:19 +0000 From: Tony Forbes <[EMAIL PROTECTED]> Subject: Re: Mersenne: Generalized Mersenne Numbers Brian J. Beesley <[EMAIL PROTECTED]> writes >Congratulations on the (unverified) discovery of the 40th Mersenne Prime. > >I was thinking (always dangerous!) about generalizing Mersenne numbers. The >obvious generalization a^n-1 is uninteresting because they're all composite >whenever a>2 and n>1. However there is an interesting generalization: > >Define GM(a,b) = a^b-(a-1), so GM(2,b) = M(b); also GM(a,1) = 1 for all a > >The distribution of primes amongst GM(a,b) for small a > 2 and small b does >seem to be interesting - some values of a seem to yield a "richer" sequence >of primes than others. Note also that, in this generalization, some >_composite_ exponents can yield primes. > >Another interesting point: the "generalized Mersenne numbers" seem to be >relatively rich in numbers with a square in their factorizations - whereas >Mersenne numbers proper are thought to be square free. (Or is that just >Mersenne numbers with prime exponents?) > >A few interesting questions: > >(a) Is there a table of status of "generalized Mersenne numbers" anywhere? Some time ago I had a look at numbers of the form 2^n - 3, i.e. GM(4, n/2). Here are my results for 3320 <= n <= 16800: 2^n - 3 is a verified prime for n = 3954, 5630, 6756, 8770, 10572, 14114. 2^n - 3 is a probable prime for n = 14400, 16460, 16680. I don't know if someone else has verified the last three. Also 2^12819 - 7 (GM(8, 4273)) is a probable prime, 2^8824 - 15 (GM(16, 2206)) is a verified prime. The verified primes were done by factorization of N+1 and N-1, and APRCL. - -- Tony _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Mon, 8 Dec 2003 09:03:06 -0600 (CST) From: "Eric W. Weisstein" <[EMAIL PROTECTED]> Subject: Mersenne: Has RSA150 ever been factored? In writing http://mathworld.wolfram.com/news/2003-12-05/rsa/ and attempting to update http://mathworld.wolfram.com/RSANumber.html, it occurred to me that I was missing a few pieces of information. Does anyone know the status of RSA150? It seems RSA 140, 155, and 160 have all been factored, but I haven't been able to find any record of RSA150's factorization. Has it just fallen by the wayside and been skipped over since RSA switched to its new binary-digits-style RSA numbers? Also, I presume RSA is no longer offering monetary prizes for RSA170 to 500. Does anyone know the status or any relevant links for these? They seem to have silently vanished from RSA's site. Best wishes, - -Eric _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 10 Dec 2003 14:50:11 +0100 From: Matthias Waldhauer <[EMAIL PROTECTED]> Subject: Mersenne: Large memory pages in Linux and Windows Server (64bit?) Hi, at first - my congratulations to all, who were involved in finding the new Mersenne prime number! Well done! And besides the fact to have found the currently largest known prime number, it also gives a nice boost to GIMPS' progress thanks to the popularity. Back to the topic: Some time ago there was a discussion going on regarding the use of large memory pages. In a mersenneforum thread I collected some info regarding new linux kernels and some real world results published in a paper. Here some extracts: Linux kernel versions 2.5.36+ and 2.6 include a "HugeTLBs" patch, which allows an application to allocate large memory pages. Also 64bit Windows Server seems to support them too: http://msdn.microsoft.com/library/default.asp?url=/library/en-us/memory/base/large_page_support.asp My thoughts about the possilibities: Oracle managed to get a 8% speedup by using the large pages. Although I have little experience in this area I think for FFTs the speedup will be much larger, because: * Even if data is already in the L1 cache the accessing time can increase if the memory addresses of these data are actually spread over many memory pages. * The limited amount of TLB entries requires fine tuning of FFT algorithms to avoid TLB thrashing as much as possible - but this avoidance could cause less efficient algorithms. * why is it so hard for large size FFTs to come at least close to the FFT MFLOPS for FFTs running completely inside L1 (or L2) cache in times of memory prefetching? * I need at least 2 mem-read/write passes to do a large size FFT - but todays max transfer rates for P4/Opteron/AFX systems (6.4GB/s = reading up to 750 times the 1024k FFT data set per second) is hardly reachable because it drops significantly for large strides. I roughly estimate that at least a speedup of 10-30% could be possible. A paper analyzed the effect of larger pages by implementing it in FreeBSD. It can be found here: http://www.cs.rice.edu/~jnavarro/superpages/ Some results: SPEC benchmark Speedup by using superpages vpr 38.3% mcf 67.6% vortex 11.2% bzip2 14.0% average for SPECint 11.2% galgel 28.9% art 12.2% lucas 28.0% apsi 82.7% average for SPECfp 11.0% and some non-SPEC benchmarks: FFTW 54.9% Matrix 654.6% Regards, Matthias Waldhauer PS: I sent this mail before with wrong sender address. If someone got it, please understand this mail as an edited version ;) _________________________________________________________________________ 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 #1096 *******************************
