# Mersenne Digest V1 #1098

`Mersenne Digest      Tuesday, December 23 2003      Volume 01 : Number 1098`
```

----------------------------------------------------------------------

Date: Sat, 13 Dec 2003 13:48:51 +0000
From: "Brian J. Beesley" <[EMAIL PROTECTED]>
Subject: Mersenne: Another thought on the L-L Test

Hi,

Another thought struck me - this could have useful applications in L-L
testing programs.

If M is the Mersenne number being tested & R(i) is the L-L residue after i
iterations, then
R(i+1) = R(i) * R(i) - 2 (modulo M) (by the statement of the L-L algorithm)

But note that (M - R(i))^2 - 2 = M^2 - 2MR(i) + R(i)^2 - 2
so (M-R(i))^2 - 2 (modulo M) is clearly equal to R(i+1).

How can this be of any use? Well, when we have a dubious iteration (say an
excessive roundoff or sum error) we can check the output by redoing the last
iteration but starting from (M-R(i)) instead of R(i) - the output should be
the same. Furthermore the action of calculating M-R(i) is very easy - just
invert all the bits.

Also, if we have suspicions about the accuracy of code when there is a high
density of 1 bits, we can try just one iteration but starting at M-4 instead
of 4. The output residual should be 14 irrespective of M (providing M>7 - as
will often be the case!). The point here is that, just as the value 4 is
represented by a string of p bits only one of which is set, M-4 is
represented by a string of p bits only one of which is unset.

Regards
Brian Beesley
_________________________________________________________________________
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: Sat, 13 Dec 2003 19:08:10 +0100
From: Alexander Kruppa <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Possible refinement of screening for Mersenne primes

Alexander Kruppa wrote:
> Brian J. Beesley wrote:
>
>> Hi,
>>
>
>> (1) Could someone with the required background please tidy up my logic
>> and prove that the assertion above is true i.e. there is no prime
>> 2^p-1 with p > 3 such that there are solutions to x^2 mod 2^p-1 =
>> 2^((p+1)/2) + 2
>
>
>
> I believe the idea is correct, but it doesn't remove candidates.
>
> Lets try (going out on a limb here, fingers crossed):
>
> [...]
>
> If p>3 and odd, 2^((p+1)/2) + 2 (mod 2^p-1) is always a QR.

That is rubbish. I was misusing the Kroecker symbol and the conclusion is wrong. (The
fact that your list contained several counterexamples should have been a strong hint!)

What my argument shows is that the number of prime factors of Mp for which
[+-]2^((p+1)/2) + 2
are QNR is always even. But that doesn't tell us whether they are QR (mod Mp) or not,
i.e. whether
they are QR modulo *every* prime factor, unless of course Mp is prime and both must be
QR modulo
the only prime "factor" there is.

Since (2^((p+1)/2) + 2) * (-2^((p+1)/2) + 2) == -2^(p+1) + 4 == -2 + 4 == 2 (mod f)
for any f|Mp, and 2 is a QR (mod f), [+-]2^((p+1)/2) + 2 must be either both be QR or
QNR. So
it suffices to check only one.

To determine whether or not they are QR (mod Mp) via quadratic reciprocity would
require knowing
the prime factorization of Mp - and knowing even one nontrivial factor would of course
settle the
question of primality as well.

One could use Euler's criterion as a check: if q is prime and gcd(r,q)==1,
r^((q-1)/2) == 1 (mod q) if r is a QR, and == -1 otherwise. If q is not prime, the
result will
usually be neither 1 or -1. We already know that 2^((p+1)/2) + 2 is a QR if Mp is
prime, so
this check will really just be a Fermat-style probable prime test which takes just as
long as a
LL test, but doesn't prove primality.

I've made a list of Mp, p<200, that are not Mersenne primes, and the Kronecker symbol
(or Legendre,
actually) of 2^((p+1)/2) + 2 (mod f) for each prime factor f of Mp. It shows that
knowing whether
[+-]2^((p+1)/2) + 2 is a QR would really eliminate a lot of candidates -  M_23, M_37,
M_47, M_59,
M_101, M_137, M_139, M_149, M_167, M_181, M_193, M_197, M199 would survive the test,
while M_11, M_29,
M_41, M_43, M_53, M_67, M_71, M_73, M_79, M_83, M_97, M_103, M_109, M_113, M_131,
M_151, M_157, M_163,
M_173, M_179, M_191 could be indentifed as composite.

Your question (2) remains open - is there a faster way to determine whether
2^((p+1)/2) + 2 is a
QR (mod Mp) than running a LL test?

When a composite Mp is completely factored, it is very easy to determine whether
2^((p+1)/2) + 2
is a QR. With enough composite Mp completely factored, maybe some kind of pattern can
be discovered
in the exponents p for which it is or isn't a QR?

Alex

M_11: ( 2^6+2 | 23 ) = -1
M_11: ( 2^6+2 | 89 ) = -1

M_23: ( 2^12+2 | 47 ) = 1
M_23: ( 2^12+2 | 178481 ) = 1

M_29: ( 2^15+2 | 233 ) = -1
M_29: ( 2^15+2 | 1103 ) = 1
M_29: ( 2^15+2 | 2089 ) = -1

M_37: ( 2^19+2 | 223 ) = 1
M_37: ( 2^19+2 | 616318177 ) = 1

M_41: ( 2^21+2 | 13367 ) = -1
M_41: ( 2^21+2 | 164511353 ) = -1

M_43: ( 2^22+2 | 431 ) = 1
M_43: ( 2^22+2 | 9719 ) = -1
M_43: ( 2^22+2 | 2099863 ) = -1

M_47: ( 2^24+2 | 2351 ) = 1
M_47: ( 2^24+2 | 4513 ) = 1
M_47: ( 2^24+2 | 13264529 ) = 1

M_53: ( 2^27+2 | 6361 ) = -1
M_53: ( 2^27+2 | 69431 ) = -1
M_53: ( 2^27+2 | 20394401 ) = 1

M_59: ( 2^30+2 | 179951 ) = 1
M_59: ( 2^30+2 | 3203431780337 ) = 1

M_67: ( 2^34+2 | 193707721 ) = -1
M_67: ( 2^34+2 | 761838257287 ) = -1

M_71: ( 2^36+2 | 228479 ) = 1
M_71: ( 2^36+2 | 48544121 ) = -1
M_71: ( 2^36+2 | 212885833 ) = -1

M_73: ( 2^37+2 | 439 ) = -1
M_73: ( 2^37+2 | 2298041 ) = -1
M_73: ( 2^37+2 | 9361973132609 ) = 1

M_79: ( 2^40+2 | 2687 ) = 1
M_79: ( 2^40+2 | 202029703 ) = -1
M_79: ( 2^40+2 | 1113491139767 ) = -1

M_83: ( 2^42+2 | 167 ) = -1
M_83: ( 2^42+2 | 57912614113275649087721 ) = -1

M_97: ( 2^49+2 | 11447 ) = -1
M_97: ( 2^49+2 | 13842607235828485645766393 ) = -1

M_101: ( 2^51+2 | 7432339208719 ) = 1
M_101: ( 2^51+2 | 341117531003194129 ) = 1

M_103: ( 2^52+2 | 2550183799 ) = -1
M_103: ( 2^52+2 | 3976656429941438590393 ) = -1

M_109: ( 2^55+2 | 745988807 ) = -1
M_109: ( 2^55+2 | 870035986098720987332873 ) = -1

M_113: ( 2^57+2 | 3391 ) = 1
M_113: ( 2^57+2 | 23279 ) = 1
M_113: ( 2^57+2 | 65993 ) = -1
M_113: ( 2^57+2 | 1868569 ) = -1
M_113: ( 2^57+2 | 1066818132868207 ) = 1

M_131: ( 2^66+2 | 263 ) = -1
M_131: ( 2^66+2 | 10350794431055162386718619237468234569 ) = -1

M_137: ( 2^69+2 | 32032215596496435569 ) = 1
M_137: ( 2^69+2 | 5439042183600204290159 ) = 1

M_139: ( 2^70+2 | 5625767248687 ) = 1
M_139: ( 2^70+2 | 123876132205208335762278423601 ) = 1

M_149: ( 2^75+2 | 86656268566282183151 ) = 1
M_149: ( 2^75+2 | 8235109336690846723986161 ) = 1

M_151: ( 2^76+2 | 18121 ) = -1
M_151: ( 2^76+2 | 55871 ) = 1
M_151: ( 2^76+2 | 165799 ) = -1
M_151: ( 2^76+2 | 2332951 ) = -1
M_151: ( 2^76+2 | 7289088383388253664437433 ) = -1

M_157: ( 2^79+2 | 852133201 ) = 1
M_157: ( 2^79+2 | 60726444167 ) = -1
M_157: ( 2^79+2 | 1654058017289 ) = -1
M_157: ( 2^79+2 | 2134387368610417 ) = 1

M_163: ( 2^82+2 | 150287 ) = 1
M_163: ( 2^82+2 | 704161 ) = 1
M_163: ( 2^82+2 | 110211473 ) = 1
M_163: ( 2^82+2 | 27669118297 ) = -1
M_163: ( 2^82+2 | 36230454570129675721 ) = -1

M_167: ( 2^84+2 | 2349023 ) = 1
M_167: ( 2^84+2 | 79638304766856507377778616296087448490695649 ) = 1

M_173: ( 2^87+2 | 730753 ) = 1
M_173: ( 2^87+2 | 1505447 ) = -1
M_173: ( 2^87+2 | 70084436712553223 ) = -1
M_173: ( 2^87+2 | 155285743288572277679887 ) = 1

M_179: ( 2^90+2 | 359 ) = -1
M_179: ( 2^90+2 | 1433 ) = -1
M_179: ( 2^90+2 | 1489459109360039866456940197095433721664951999121 ) = 1

M_181: ( 2^91+2 | 43441 ) = 1
M_181: ( 2^91+2 | 1164193 ) = 1
M_181: ( 2^91+2 | 7648337 ) = 1
M_181: ( 2^91+2 | 7923871097285295625344647665764672671 ) = 1

M_191: ( 2^96+2 | 383 ) = 1
M_191: ( 2^96+2 | 7068569257 ) = -1
M_191: ( 2^96+2 | 39940132241 ) = 1
M_191: ( 2^96+2 | 332584516519201 ) = 1
M_191: ( 2^96+2 | 87274497124602996457 ) = -1

M_193: ( 2^97+2 | 13821503 ) = 1
M_193: ( 2^97+2 | 61654440233248340616559 ) = 1
M_193: ( 2^97+2 | 14732265321145317331353282383 ) = 1

M_197: ( 2^99+2 | 7487 ) = 1
M_197: ( 2^99+2 |
26828803997912886929710867041891989490486893845712448833 ) = 1

M_199: ( 2^100+2 | 164504919713 ) = 1
M_199: ( 2^100+2 | 4884164093883941177660049098586324302977543600799 ) = 1

_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ      -- http://www.tasam.com/~lrwiman/FAQ-mers

------------------------------

Date: Sun, 14 Dec 2003 10:21:51 -0600
From: Stephen Whitis <[EMAIL PROTECTED]>
Subject: Mersenne: Smallest Prime Number Discovered, Soon After Largest

From a Satire site...
http://theeschalot.com/smallest-prime-number-discovered.html

Smallest Prime Number Discovered, Soon After Largest

DETROIT - Wallace Bonownski says you don't have to have
200,000 computers and a grad student to discover a new
prime number. "You just gotta use yer thinker, is all," said
the Michigan State University groundskeeper. "I heard about
Michael's big find, and I thought, 'Hey, if that's the largest
prime number, then I'll bet the negative version would be
the smallest. And I discovered it!'"

(continues)

_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ      -- http://www.tasam.com/~lrwiman/FAQ-mers

------------------------------

Date: Sun, 14 Dec 2003 07:03:33 -0600
From: [EMAIL PROTECTED] (Mikus Grinbergs)
Subject: Mersenne: PrimeNet response

Was using the PrimeNet manual entry page.
It responded as expected to my input,
but the response included the line

----- rate regulated at 0.50 Hz -----

What is that line telling me ???

mikus
_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ      -- http://www.tasam.com/~lrwiman/FAQ-mers

------------------------------

Date: Tue, 23 Dec 2003 10:42:45 +0000
From: Nick Craig-Wood <[EMAIL PROTECTED]>
Subject: Mersenne: Large memory pages in Linux

On Wed, Dec 10, 2003 at 06:26:54PM +0000, Nick Craig-Wood wrote:
> I'm in the process of writing (not quite finished or working ;-) some
> code which you load as an LD_PRELOAD library under linux.  This gets
> its fingers into the memory allocation, and makes all malloc space
> come from hugetlbfs (how you get large pages under linux).
>
> My primary user for this was to be mprime of course!

Well I finished the code and here are the results on my lowly laptop
running 2.6.0.

Intel(R) Pentium(R) III processor
CPU speed: 550.78 MHz
CPU features: RDTSC, CMOV, PREFETCH, MMX, SSE
L1 cache size: 16 KB
L2 cache size: 256 KB
L1 cache line size: 32 bytes
L2 cache line size: 32 bytes
TLBS: 64
Prime95 version 22.12, RdtscTiming=1

Normal
- ------

Best time for 256K FFT length: 80.256 ms.
Best time for 320K FFT length: 101.820 ms.
Best time for 384K FFT length: 125.191 ms.
Best time for 448K FFT length: 145.505 ms.
Best time for 512K FFT length: 161.178 ms.
Best time for 640K FFT length: 215.113 ms.
Best time for 768K FFT length: 258.055 ms.
Best time for 896K FFT length: 304.786 ms.
Best time for 1024K FFT length: 345.747 ms.
Best time for 1280K FFT length: 449.540 ms.
Best time for 1536K FFT length: 541.963 ms.
Best time for 1792K FFT length: 661.651 ms.

With all memory allocations coming from 4 MB pages
- --------------------------------------------------

Best time for 256K FFT length: 79.293 ms.   1.2%
Best time for 320K FFT length: 102.032 ms. -0.2%
Best time for 384K FFT length: 124.022 ms.  0.9%
Best time for 448K FFT length: 145.492 ms.  0.0%
Best time for 512K FFT length: 161.568 ms. -0.2%
Best time for 640K FFT length: 213.311 ms.  0.8%
Best time for 768K FFT length: 254.609 ms.  1.3%
Best time for 896K FFT length: 301.911 ms.  0.9%
Best time for 1024K FFT length: 339.203 ms. 1.9%
Best time for 1280K FFT length: 439.119 ms. 2.3%
Best time for 1536K FFT length: 531.422 ms. 1.9%
Best time for 1792K FFT length: 645.350 ms. 2.5%

So consistent but small improvements in the larger FFTs.  This just
goes to show what a good job George has done in not thrashing the TLB!

I wonder if Prime95 could be made more efficient if it didn't have to
worry about the TLB?  Its obviously detecting the TLB slots for this
computer which is wrong in this case - perhaps there is a way of
overriding this?

Please email me if you'd like to experiment with the code - its quite
simple (it just took rather a lot of different approaches to get
right!).  You'll need to be running 2.6.0 with HUGETLB support if you
want to play (see hugetlbpage.txt in Documentation in the kernel

- --
Nick Craig-Wood
[EMAIL PROTECTED]
_________________________________________________________________________
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 #1098
*******************************

```