Talk:Factors of a Mersenne number

From Rosetta Code

Algorithm incorrect?[edit]

In testing some other Mersenne numbers, I get false negatives from the Python program. Both M59 and M6007 are not prime and should yield a factor, right? If this is expected, maybe some more clarification is needed in the description. --IanOsgood 19:28, 16 January 2009 (UTC)

I think the arbitrary limit of (16384 / p) is too small for those cases. I found a factor for M59 by increasing the limit. But I don't know how to determine what is a good limit to use. In the worst case we can just use sqrt(Mp) as the limit I guess. That will make testing the actual prime cases take really long. --Spoon! 19:59, 16 January 2009 (UTC)

"q must be prime." It doesn't need to be prime. If you are searching for Mersenne divisors it is efficient only to search for prime factors - but it doesn't need to be. In fact this ModPow can be used for Probable Prime tests.

"This method only works for Mersenne numbers where P is prime (M27 yields no factors)." It also works for composite exponents. Even the example you gave will find the factor 73 of M27, but 73 is really a factor of M9 and M27/M9 is indeed prime. But in general it does find real factors of composite exponent Mersennes.

Mathematica has a very efficient ModPow built in.

Paul Landon