Thread: Factors of Mersenne Numbers View Single Post 2002-09-25, 17:38 #8 ewmayer ∂2ω=0   Sep 2002 República de California 2×5,813 Posts toferc wrote (re. the special form 2qk + 1 of Mersenne factors) >We know that 2 is a quadratic residue mod p because > >q is odd -> qk is odd -> qk + 1 is even -> >2^(qk+1) is a perfect square -> >2*(2^qk) is a perfect square Not quite. In fact, qk may be even or odd. Example the factors of M11 = 2^11 - 1 are 23 and 89; the first has k = 1 which gives qk = 11, the second has k = 4, which gives qk = 44. But in fact it's much easier to show that 2 is a quadratic residue modulo the factor p. First off, only factors of Mq with q odd have the special form in question, so we only consider odd-prime q. Simply from the fact that p divides Mq, we have 2^q == 1 mod p. Multiplying by 2, we have 2^(q+1) == 2 mod p, and since q odd, the exponent of 2 in the left-hand side is even, i.e. the LHS is a perfect square. Another thing that bears mentioning is that in fact there are additional rigorous correlations between the Mersenne exponent q modulo 3,4,5,... and k mod 3,4,5,... . Exploiting the simplest few of these can reduce the number of k's we need to try to achieve a desired factor-size bound by 75-80%. All the good factoring codes (including Prime95) do this, and also subject all candidates that survive the basic criteria (p = +- 1 mod 8, p has k of the proper form modulo 3,4,5...) to a further small- prime sieve to increase the odds that the candidate factor is prime. (Q Why don't we just subject p to a probable-prime test? Answer Because doing that is about the same expense as testing whether 2^q == 1 mod p. In fact, if p has more bits than the Mersenne exponent q, which is generally the case for decently deep trial factoring work, it's MORE expensive to test p for probable primality than to test whether it divides Mq. Plus, if p did prove to be probable-prime, we'd have to go ahead and see whether it divides Mq anyway.) -Ernst  