Talk:Factors of a Mersenne number: Difference between revisions
(New page: == Algorithm incorrect? == In testing some other Mersenne numbers, I get false negatives from the Python program. Both M<sub>59</sub> and M<sub>6007</sub> are not prime and should yield a...) |
|||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
== Algorithm incorrect? == |
== Algorithm incorrect? == |
||
In testing some other Mersenne numbers, I get false negatives from the Python program. Both M<sub>59</sub> and M<sub>6007</sub> are not prime and should yield a factor, right? If this is expected, maybe some more clarification is needed in the description. --[[User:IanOsgood|IanOsgood]] 19:28, 16 January 2009 (UTC) |
In testing some other Mersenne numbers, I get false negatives from the Python program. Both M<sub>59</sub> and M<sub>6007</sub> are not prime and should yield a factor, right? If this is expected, maybe some more clarification is needed in the description. --[[User:IanOsgood|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 M<sub>59</sub> 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(M<sub>p</sub>) as the limit I guess. That will make testing the actual prime cases take really long. --[[User:Spoon!|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 |
|||
Latest revision as of 15:06, 6 February 2010
Algorithm incorrect?
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