Factor found on M809

jocelynl · 2003-01-18, 13:42

Hi George,

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

smh · 2003-01-18, 14:15

From the ECMNET page (the c120-355 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?

Prime95 · 2003-01-18, 15:14

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.

cperciva · 2003-01-18, 17:46

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

smh · 2003-01-18, 20:18

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

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

nuutti · 2003-01-20, 12:55

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

Yours,

Nuutti

philmoore · 2003-01-21, 18:16

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!

smh · 2003-01-21, 19:11

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.

philmoore · 2003-02-03, 01:30

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.

patrik · 2003-02-27, 20:37

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 :( .

philmoore · 2003-02-27, 21:31

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!

2003-01-18, 13:42	#1
jocelynl Sep 2002 2×131 Posts	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?

2003-01-20, 12:55	#6
nuutti Jan 2003 31 Posts	Records site I think that here is a kind of record list : http://www.cerias.purdue.edu/homes/ssw/cun/champ Yours, Nuutti

2003-02-03, 01:30	#9
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 3×373 Posts	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 18701e6 (C. Curry) + 50403e6 (Curry) + 205111e6 (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=2331 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.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Factor found that should have been found by P-1	tha	Data	65	2020-08-05 21:11
F12 factor found?	johnadam74	FermatSearch	16	2016-11-03 12:10
found this factor	tha	Factoring	4	2007-06-18 19:56
After a factor is found it keeps on going	jocelynl	Software	6	2004-08-07 01:31
Odd Reporting of a Factor Found	Reboot It	Data	3	2003-12-03 14:39

2003-01-18, 14:15	#2
smh "Sander" Oct 2002 52.345322,5.52471 4A5₁₆ Posts	From the ECMNET page (the c120-355 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?

2003-01-18, 15:14	#3
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 2·53·71 Posts	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.

2003-01-18, 17:46	#4
cperciva Oct 2002 43 Posts	Richard Brent (who happens to be my DPhil supervisor) says that he thinks this is the current SNFS record.

2003-01-18, 20:18	#5
smh "Sander" Oct 2002 52.345322,5.52471 4A5₁₆ Posts	As far as i know, the old record was 2^773 + 1 (233 digits) ftp://ftp.cwi.nl/pub/herman/SNFSrecords/SNFS-233

2003-01-21, 18:16	#7
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 3·373 Posts	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!

2003-01-21, 19:11	#8
smh "Sander" Oct 2002 52.345322,5.52471 29·41 Posts	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.

2003-02-27, 20:37	#10
patrik "Patrik Johansson" Aug 2002 Uppsala, Sweden 1A9₁₆ Posts	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 :( .

2003-02-27, 21:31	#11
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 2137₈ Posts	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!