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.