How hard is a 140-digit GNFS?

fivemack · 2007-02-09, 23:13

With ggnfs, 100 digits is an easy overnight run on one CPU of the machine at work, eight or nine hours, and ggnfs is about twice as fast as mpqs at this point. 120 digit runs seems to take about five 24-hour days, start to end, so fifteen times longer. Is it realistic to extrapolate that 140 digits would take on the order of three CPU-months? (that is, somewhere between 500 and 1000 MIPS-years in the units the RSA155 paper used)

Sieving's parallel, polynomial selection is parallel; the matrix isn't really problematic at 140 digits. I suppose I'm looking for references for the trade-off between polynomial selection time and run-time - this has clearly been done, there's a table in the RSA155 write-up, but I haven't seen it done in more detail than that.

Is there also a reference for picking the right number of special-q to sieve on before starting merging relations?

Am there more complicated trade-offs, like the choice of the number of large primes to permit in the relations, which are important at this level and which I've just been letting factLat.pl pick for me?

akruppa · 2007-02-10, 08:41

I'm doing a GNFS c140 right now, sieving seems to take about 100 days on a 2GHz Athlon.

Alex

akruppa · 2007-02-10, 20:48

Oh, oops... that estimate is for elapsed time, but I'm only sieving during the day. So cpu time should be about 50 days on 2GHz.

Alex

geoff · 2007-02-16, 03:52

I did a C140 with ggnfs, the result is posted here.

I had a lot of difficulty solving the matrix (matsolve failed to converge 5 times), but I don't think it was directly related to the size of the composite. I am having similar problems now with a difficulty 192 SNFS matrix (5,411+), although I have solved more difficult matrices with ggnfs and had no problems at all.

2007-02-09, 23:13	#1
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2³×11×73 Posts	How hard is a 140-digit GNFS? With ggnfs, 100 digits is an easy overnight run on one CPU of the machine at work, eight or nine hours, and ggnfs is about twice as fast as mpqs at this point. 120 digit runs seems to take about five 24-hour days, start to end, so fifteen times longer. Is it realistic to extrapolate that 140 digits would take on the order of three CPU-months? (that is, somewhere between 500 and 1000 MIPS-years in the units the RSA155 paper used) Sieving's parallel, polynomial selection is parallel; the matrix isn't really problematic at 140 digits. I suppose I'm looking for references for the trade-off between polynomial selection time and run-time - this has clearly been done, there's a table in the RSA155 write-up, but I haven't seen it done in more detail than that. Is there also a reference for picking the right number of special-q to sieve on before starting merging relations? Am there more complicated trade-offs, like the choice of the number of large primes to permit in the relations, which are important at this level and which I've just been letting factLat.pl pick for me?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Hard reboot	dans	Hardware	5	2009-12-30 08:22
160 digit factor found of 366 digit (PRP-1)	AntonVrba	Factoring	7	2005-12-06 22:02
ECM puzzle (hard)	akruppa	Puzzles	1	2005-09-08 19:08
Learning About RAM the Hard Way	Longshot	Hardware	5	2005-05-21 16:40
wow...1 Tb hard drive	ixfd64	Hardware	8	2004-06-03 20:37

2007-02-10, 08:41	#2
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	I'm doing a GNFS c140 right now, sieving seems to take about 100 days on a 2GHz Athlon. Alex

2007-02-10, 20:48	#3
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	Oh, oops... that estimate is for elapsed time, but I'm only sieving during the day. So cpu time should be about 50 days on 2GHz. Alex

2007-02-16, 03:52	#4
geoff Mar 2003 New Zealand 13×89 Posts	I did a C140 with ggnfs, the result is posted here. I had a lot of difficulty solving the matrix (matsolve failed to converge 5 times), but I don't think it was directly related to the size of the composite. I am having similar problems now with a difficulty 192 SNFS matrix (5,411+), although I have solved more difficult matrices with ggnfs and had no problems at all.