M673 completely factored

[philmoore]

It was announced today that M673, the smallest Mersenne number which had not been completely factored into its prime factors, was factored by the Number Field Sieve NFSNET group:

http://www.nfsnet.org/ann-2_673M_1.html

M673 at 203 digits had two known prime factors, 581163767 and 41283139633378645724930694480520226273492263, a 44-digit factor discovered by ECM using mprime. The remaining 151-digit composite cofactor split into a 59-digit prime factor and a 92-digit prime factor listed on the web-page given above. Using prime95 (mprime) ECM, I calculate that the 59-digit factor would have turned up approximately once every 700,000 curves with the stage 1 bound set to 44,000,000. Not real encouraging, but then with the 5596 curves currently listed on the status page, that still translates into a 1 in 125 chance of finding a huge factor by ECM standards: the current record is 55-digits. Hopefully, ECM enhancements can double the efficiency of the program.

M713 is now the smallest Mersenne number which is not completely factored. The exponent 713=23*31 is composite, and M739 is the smallest with a prime exponent.

[philmoore]

Congratulations to Patrik Johansson, who just yesterday completed the factorization of M731 by finding a 48-digit factor using ECM. According to the ECMNET page:
http://www.loria.fr/~zimmerma/records/ecmnet.html
Patrik did the first stage of ECM using mprime and then did the second stage using GMP-ECM. The 135-digit cofactor is also prime, so this Mersenne number is completely factored. It was the second smallest Mersenne number which had not been completely factored, M713 being the smallest. Patrik just saved the NFSNET people a lot of work - give him points for conservation of cycles!