2^1157-1 c182=p91.p92 by GNFS (!)

Batalov · 2009-06-19, 01:50

Speechless..!

5723 2,1157- c182 3031775395304168658687668034006122436307098537451179184205695859116954116590723393806112159. p92 Bos+Kleinjung gnfs

Bravo!

Andi47 · 2009-06-19, 04:47

Wow!!

10metreh · 2009-06-19, 06:21

3rd largest GNFS ever!

fivemack · 2009-06-19, 13:03

Nice result! As Serge knows, they have just shot the only accessible fox in the field; the next-smallest Cunningham cofactor with SNFS difficulty above 300 is the barely-a-C192 from 2^1087-1.

CADO or msieve for the completion?

Joppe Bos is one of the people with the big PS3 cluster at LACAL; I wonder if they managed to get sieving on the Cell working. I'd have thought the limit of 200MB memory per machine (20 bytes per factor-base element) was an insuperable obstacle, but Kleinjung is exceptionally clever.

I'd expect that the PS3 cluster is currently hunting SHA-1 collisions.

jasonp · 2009-06-19, 13:19

Quote:

Originally Posted by fivemack

CADO or msieve for the completion?

My guess is neither; Kleinjung et. al. have their own postprocessing code.

Batalov · 2009-06-19, 15:40

Well, as anyone may by now have observed, their next target is a gnfs-192 cofactor of 2¹¹⁷⁵-1

Indeed all other foxes on the road to gnfs-192 look unconvincing (0.68-0.69 ratios)

fivemack · 2009-06-19, 16:33

I'm just slightly surprised they didn't take 2,1087- C192 (0.5837) which is slightly smaller with a better ratio. I'm reasonably confident that 2,1099+ C182 (0.6409) is easier by GNFS than SNFS.

The C182 would be entirely plausible for mersenneforum using my i7 to solve the matrix; the C192 is probably more plausible than 2^941-1 but I think not to the point of being plausible - really needs parallel equipment for the matrix, and I don't think I can justify to myself the £2300 price, the £3/day electricity use or the kilowatt heat generation from four Infiniband-connected Shanghai boxes.

Batalov · 2009-06-19, 16:48

Upon better sorting of the list (and accounting for quartic unusability), these also come to mind (for the forum):

Code:

183	5, 383-  	267.7	0.683587
184	2, 1040+  	250.4	0.734657	"quartic"
185	2, 899-  	270.6	0.683600
186	10,750L  	300	0.620000	"quartic"
188	7, 347+  	293.2	0.641093
192	2, 1087-  	327.2	0.586762
192	2, 1175-  	282.9	0.678521	"quartic" Bos+K gnfs

(The difficulties are shown as if quartics were possible at that size.)

R.D. Silverman · 2009-06-19, 18:13

Quote:

Originally Posted by Batalov

Upon better sorting of the list (and accounting for quartic unusability), these also come to mind (for the forum):

Code:

183	5, 383-  	267.7	0.683587
184	2, 1040+  	250.4	0.734657	"quartic"
185	2, 899-  	270.6	0.683600
186	10,750L  	300	0.620000	"quartic"
188	7, 347+  	293.2	0.641093
192	2, 1087-  	327.2	0.586762
192	2, 1175-  	282.9	0.678521	"quartic" Bos+K gnfs

(The difficulties are shown as if quartics were possible at that size.)

Why discard 2,899-? Easier by SNFS?

There are also 2,2110M C191, 2,2158M C193, 2,2090M C191 or slightly more
ambitious, 2,1196+ C197

Andi47 · 2009-06-19, 19:21

Quote:

Originally Posted by fivemack

the C192 is probably more plausible than 2^941-1 but I think not to the point of being plausible - really needs parallel equipment for the matrix, and I don't think I can justify to myself the £2300 price, the £3/day electricity use or the kilowatt heat generation from four Infiniband-connected Shanghai boxes.

It would be interesting how T.Rex's 8-core Nehalem Rocket scales for huge NFS postprocessing...

akruppa · 2009-06-22, 20:17

Here are some details about the factorization Joppe sent me:

Quote:

Originally Posted by Joppe Bos

Hi Alex,

Here some details (partially provided by Thorsten).

Polynomial selection was done by Thorsten:
"According to the log files and other files in that directory I ran one part of the polynomial selection for less than 5 month on one core and another part for 1.5 month on 1-6 cores on a different machine."
The polynomial used is:

Code:

#skewness 151223529.05 norm 3.38e+25 alpha -8.36 Murphy_E 7.24e-14
X5 319200
X4 154373575683904
X3 -23186446035652343324670
X2 -2829704335434860171409679177683
X1 303706077386585938118284771853918274616
X0 -3824969268526247936633040832393600441093924020
Y1 50201288567936759
Y0 -165897258160957887730516436168795993
M 26187125732864623607010592600170521548519803304553527794057061364034844248129814228791611244460413159396080085931821815721579483336211552879481069712975214746318048280605646526340956
0 64000000 3.82 34 99
0 128000000 3.68 34 99

I did the sieving using the Greedy cluster (see http://greedy.epfl.ch?pageLang=en). This took approximately 5-6 weeks (running nighttime only), the number of cores I got varied a lot and we used the relatively slow Windows binary.

Thorsten ran the matrix on our cluster (using a part of it) with the block Wiedemann implementation. The matrix: 32743714 * 32743202 wt 3728252442. Thorsten told me that: "It took 12 day wall clock time on up to 32*4 cores (2.66GHz Intel Xeon), but there was some idle time (<=9 days should have been possible, perhaps less)."

If you want more information just let me know.

Best regards,

Joppe

Alex

2009-06-19, 01:50	#1
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	2^1157-1 c182=p91.p92 by GNFS (!) Speechless..! 5723 2,1157- c182 3031775395304168658687668034006122436307098537451179184205695859116954116590723393806112159. p92 Bos+Kleinjung gnfs Bravo!

2009-06-19, 16:33	#7
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²×131 Posts	I'm just slightly surprised they didn't take 2,1087- C192 (0.5837) which is slightly smaller with a better ratio. I'm reasonably confident that 2,1099+ C182 (0.6409) is easier by GNFS than SNFS. The C182 would be entirely plausible for mersenneforum using my i7 to solve the matrix; the C192 is probably more plausible than 2^941-1 but I think not to the point of being plausible - really needs parallel equipment for the matrix, and I don't think I can justify to myself the £2300 price, the £3/day electricity use or the kilowatt heat generation from four Infiniband-connected Shanghai boxes. Last fiddled with by fivemack on 2009-06-19 at 16:57

2009-06-19, 16:48	#8
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	Upon better sorting of the list (and accounting for quartic unusability), these also come to mind (for the forum): Code: ~~183 5, 383- 267.7 0.683587~~ 184 2, 1040+ 250.4 0.734657 "quartic" ~~185 2, 899- 270.6 0.683600~~ 186 10,750L 300 0.620000 "quartic" 188 7, 347+ 293.2 0.641093 192 2, 1087- 327.2 0.586762 192 2, 1175- 282.9 0.678521 "quartic" Bos+K gnfs (The difficulties are shown as if quartics were possible at that size.)

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
3,697+ (GNFS 220.9)	pinhodecarlos	NFS@Home	0	2014-12-24 19:13
3,766+ (GNFS 215.5)	pinhodecarlos	NFS@Home	34	2014-04-01 21:27
c97 GNFS not possible?	Andi47	Msieve	5	2009-01-26 18:19
6^383+1 by GNFS is complete. Thanks!	fivemack	Factoring	50	2008-03-24 19:57
The factors of 2,1137P.c182 are p78 * p104	Jeff Gilchrist	NFSNET Discussion	0	2004-06-09 14:15

2009-06-19, 04:47	#2
Andi47 Oct 2004 Austria 2×17×73 Posts	Wow!!

2009-06-19, 06:21	#3
10metreh Nov 2008 4422₈ Posts	3rd largest GNFS ever!

2009-06-19, 13:03	#4
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²×131 Posts	Nice result! As Serge knows, they have just shot the only accessible fox in the field; the next-smallest Cunningham cofactor with SNFS difficulty above 300 is the barely-a-C192 from 2^1087-1. CADO or msieve for the completion? Joppe Bos is one of the people with the big PS3 cluster at LACAL; I wonder if they managed to get sieving on the Cell working. I'd have thought the limit of 200MB memory per machine (20 bytes per factor-base element) was an insuperable obstacle, but Kleinjung is exceptionally clever. I'd expect that the PS3 cluster is currently hunting SHA-1 collisions.

2009-06-19, 15:40	#6
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2505₁₆ Posts	Well, as anyone may by now have observed, their next target is a gnfs-192 cofactor of 2¹¹⁷⁵-1 Indeed all other foxes on the road to gnfs-192 look unconvincing (0.68-0.69 ratios)