(Posted this to mersenneforum.org yesterday, but forgot to cc: it to
the mailing list)
The following three factors of the double-Mersenne number M(M31) (where
we write factors as q = 2*k*p+1, with p = 2^31-1) were previously known:
295257526626031 # k = 68745 (Guy Haworth, 1983)
87054709261955177 # k = 20269004 (Wilfrid Keller, 1994)
242557615644693265201 # k = 56474845800 (Reto Keiser & Tony Forbes,
1999)
To the best of my knowledge, the following was not:
178021379228511215367151 # k = 41448832329225 .
This was found on the afternoon of 19 June 2005 using a sieving program
of my own writing. The code uses the above well-known special form of
prime-exponent Mersenne factors along with the property q == +-1
(modulo 8) (which follows from 2 being a quadratic residue modulo any
2^n-1 with odd exponent n) and a small-prime sieve (using primes <=
611957) to eliminate over 90% of the remaining candidate q's. The
surviving factor candidates were tested using a fast left-to-right
binary powering algorithm and a 96-bit Montgomery-style modmul.
("96-bit" means that we first calculate an inverse of each q modulo
2^96, and intermediate products are as large as 192 bits. Note that in
my implementation, I actually found it more convenient to calculate the
inverse power 2^(-p) modulo each candidate q via the Montgomery modmul.)
The sieving code used a high-level C implementation with small
assembly-code macros to calculate 64x64=>128-bit unsigned integer
products on processors with hardware support for same. Running in
parallel on a mix of Alpha ev6 and Itanium processors, the new factor
was discovered after roughly 15 GHz-days of total processing time
(slightly less than one calendar day, running on 16 processors at once)
had elapsed and 2*10^12 factor candidates been tested (which works out
to roughly 1000 CPU cycles to test each candidate q).
By way of reference, a webpage on the current factorization status of
double-Mersennes is maintained by Will Edgington at
http://www.garlic.com/~wedgingt/MMPstats.txt .
Best regards,
Ernst Mayer
_______________________________________________
Prime mailing list
[email protected]
http://hogranch.com/mailman/listinfo/prime
