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 oddprime 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 lefthand 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 factorsize bound by 7580%. 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 probableprime 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 probableprime, we'd have to go ahead and
see whether it divides Mq anyway.)
Ernst
