View Single Post
Old 2002-09-14, 18:05   #6
toferc
 
Aug 2002

2·3·5 Posts
Default

Quote:
Originally Posted by asdf
you left one question unanswered (unless I missed it somewhere) but does k need to be in a certain form?
Or can it be any random number (of course 2kp+1 might not divide the mersenne number if k is random)?
I also note that you used an r, and you substituted it with a 2k because it is even. Therefore, what are the bounds of testing for k?


Thanks.
The only restriction on the number k is that it is a nonnegative integer. For example, M11 = 2^11 - 1 = 2047 has the divisors 1, 23, 87 and 2047.

1 = 2*0*11 + 1 (k=0)
23 = 2*1*11 + 1 (k=1)
87 = 2*4*11 + 1 (k=4)
2047 = 2*93*11 + 1 (k=93)

We *can* say that if Mp is not prime, then it has a factor other than 1 which is less than the square root of Mp. Thus only values of k for which

2kp + 1 < sqrt(Mp)

need to be checked. This doesn't really limit k all that much unless p is really small. A rough bound can be found as follows:

sqrt(Mp) = sqrt(2^p - 1) < sqrt(2^p) = 2^(p/2)

2kp + 1 < 2^(p/2)
2kp < 2^(p/2)
kp < 2^(p/2 - 1)
k < 2^(p/2 - 1) / p

If you try 11, you get
k < 2^(4.5) / 11 = (approx) 2.057 < 3

So if you tried k=1 and k=2 and neither one resulted in a factor of M11, you would know M11 is prime.

If p gets just a little bigger, the bound for k gets quite large. Substituting 127 gives you
k < 2^(62.5) / 127 = (approx) 5.1 * 10^16
Which is an awful lot of k's.

What is done in practice is that some small values of (2kp+1) are tried. This produces factors for quite a lot of Mp's. At a certain point, it doesn't pay off to try any more k's, because the bigger k is, the less chance (2kp + 1) is a factor.
toferc is offline   Reply With Quote