Factor found on M809
 

Hi George,

I noticed that a factor was found on M809. Do you know who found it and what method as been used?

From the ECMNET page (the [url=http://www.loria.fr/~zimmerma/records/c120-355]c120-355[/url] page):
[list] 244 2, 809- 3414023389634485388328884116849283992138116261025744978122883999623187065762627620618973286846235796//
244 ........... 8603801142238378191082950664469091149211460382987933849836007206807111754539330960823868487806612300//
244 ........... 88261573940214625662995187948181075905216511
t35 Curry + 19204*44e6 Franke t50
done 4148386731260605647525186547488842396461625774241327567978137 Franke et al. 03.01.03 SNFS
removed[/list:u]
Is this a record size SNFS factorization?

Sieving was done at the CWI, at the Scientific Computing Institute and the
Pure Mathematics Department at Bonn University, and using private resources
of J. Franke, T. Kleinjung and the family of F. Bahr. The linear algebra step
was done by P. Montgomery at SARA in Amsterdam. Postprocessing (other than
the block Lanczos step) was done in Bonn


I do not know if this is a record SNFS factorization.

Richard Brent (who happens to be my DPhil supervisor) says that he thinks this is the current SNFS record.

As far as i know, the old record was 2^773 + 1 (233 digits)

[url]ftp://ftp.cwi.nl/pub/herman/SNFSrecords/SNFS-233[/url]

Records site
 

I think that here is a kind of record list :
http://www.cerias.purdue.edu/homes/ssw/cun/champ


Yours,

Nuutti

Thanks to Jocelyn and Sander for raising the question and finding the answer. I had been curious about M809 and had been hoping for some kind of announcement from the factorers. 244 digits - wow! Unfortunately, the smaller factor was "almost" in reach of ECM. I had been hoping for a new penultimate factor record, which is currently the 98-digit factor of M727 found by Dodson/AKL/CWI, but sooner or later, this record will fall, too!

If you call 61 digits "almost" then you're right ;)

I had seen the page nuutti gave before, just couldn't find it straight away.
[list]Special number field sieve by SNFS difficulty:
4703 C227 2,751- CWI/Dodson/Franke/AKL/Leyland
4530 C227 2,773+ The Cabal[/list:u]

Just wondering, why has 2,751- a higher SNFS difficulty? 2,773+ seems larger.

Another one
 

Here's another one, the completed factorization of M719, from the same page cited by smh above:

208 2, 719- 2481831853628975239734324283683350274917109400971062161087619357919015825532905467342080904365328434$
208 4339425991997685971628441277106032413489516858866309585344149133273061723293256127420536552444883737$
208 54631919
1870*1e6 (C. Curry) + 5040*3e6 (Curry) + 2051*11e6 (Curry) t40
done 737572843389436536903316910033561929012829990389769 Dodson/AKL/CWI/Leyland SNFS 07.01.03

This 51-digit factor probably could have been found more easily with about one year's worth of ECM on a fast P4 or Athlon. My guess is that the factorers found M719 a tempting target because the unfactored part, at 208 digits, seemed to offer a possibility of breaking the 98-digit penultimate factor record.

I see that the NFSNet project: http://www.nfsnet.org/
has started work on M673, the smallest Mersenne number not yet completely factored. The next two Mersenne numbers on the list, M713 and M731, have had considerably less ECM effort than M673, probably because the exponents are composite. (713=23*31 and 731=17*43.) Is anyone feeling lucky? Finding a factor of either of these could save the SNFS folks a lot of work down the road! See:
http://www.mersenne.org/ecmm.htm
for ECM status.

So, which number should we do first, M713 or M739, where 739 is prime? I can put three P4's to work for one or two weeks.

Note: M739 was affected by the bug in version 22.12 and earlier, and I ran 5000 curves up to B1=11000000. Now I've just rerun them, with the corrected version, but I didn't find any factor :( .

I'd say all three numbers, M713, M731, and M739 look like good candidates. You could put each P4 to work on a different candidate! M713 has a C171 cofactor, M731 has a C183 cofactor, and M739 has a C168 cofactor. I've already run about 300 curves on M713 with B1=44000000 on an old 233 MHz Pentium! My guess is that we don't always know how much work has been done by the ECMNET group, and that at B1=44000000, there is a reasonable chance that a record ECM factor of > 55 digits just possibly could show up.

Sorry to hear that your M739 curves were affected by the bug. That bug was an unusual one, affecting exponents near FFT boundaries.

Good luck!

Has anyone tried doing stage 1 prime95 and stage 2 in ecm-gmp 5.0? Ecm-gmp has a vastly superior stage 2.

Even better for the ambitious reader would be taking the ecm-gmp sources and integrating the mprime FFT routines.

Is it safe to assume this is far more than a "cut and paste"?

Also, would the GMP-ECM folks mind the loss of portability?

[quote="pakaran"]Is it safe to assume this is far more than a "cut and paste"?[/quote]

Yes, changing the source code would be tricky.

As to running stage 1 in prime95/mprime and stage 2 in ecm-gmp that shouldn't be too much harder than some cut/paste/scripts. The hooks are in prime95 to output the stage 1 result, and I asked Paul to implement a hook to accept a stage 1 result and only run stage 2.

ecm-gmp's stage 2 is more than twice as effective at finding factors than prime95.

Thanks for the quick reply George.

I know little about C and ASM beyond what I learned in my 300-level programming languages course, so I guess I'm not the one to do it :(.

Is there any reason the more effective Phase 2 code couldn't be implimented in a future version of Prime95?

Does it take longer than the current Prime code?

[quote="Prime95"]Has anyone tried doing stage 1 prime95 and stage 2 in ecm-gmp 5.0? Ecm-gmp has a vastly superior stage 2.
[/quote]

I'm still looking for a windows binary (pref. an optimized P4 version).

Anyone out there who has one ?