Double Mersennes Prime Search



Let d be a prime divisor of MMp. We know that

    A factor d will always be of the form 2*k*m + 1 where m = M(p) = 2p - 1 is a Mersenne prime.

Note that, since m == 1 (mod 3), factors of M(m) cannot have k == 1 (mod 3),
since 2*k*m + 1 == 0 (mod 3) in that case.

Chris Nash pointed out on the Mersenne list (1999 Sep 22) that, for odd Mersenne exponents, k must be 0 or 1 mod 4,
since, otherwise, 2 is not a quadratic residue of the supposed factor.

The combination of the prior two restrictions limits k to 0, 5, 8, and 9 modulo 12.

The program uses a sieving process. We start with a long list of ks and we reject all those ks for which the corresponding factor d is divisible by a prime q = 3, 5, 7, 11, ...
up to some suitable limit.
For each k that survives we compute d and see if it divides into MMp.
All calculations are done modulo d.

© MoreWare 2012