View Single Post
Old 2002-09-25, 17:38   #8
ewmayer's Avatar
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.)

ewmayer is offline   Reply With Quote