Msieve NFS minimum size

10metreh · 2008-12-06, 20:54

Why does msieve's NFS require the number to be at least 97 digits? SNFS is much faster than QS for lower levels than that. Even just postprocessing will switch to the quadratic sieve instead.

jasonp · 2008-12-07, 02:26

Reports from users (admittedly old now) put the crossover point between msieve's QS and the GGNFS tools at 94-100 digits. Admittedly this sucks if you are completing a <97 digit job started by GGNFS. I can make the limit smaller, but I've already had a case of a public project try to use msieve for 20-digit NFS for instructional purposes.

I'll put in logic that uses NFS for postprocessing even if the input is smaller than the bound.

10metreh · 2008-12-07, 09:34

Quote:

Originally Posted by jasonp

I've already had a case of a public project try to use msieve for 20-digit NFS for instructional purposes.

LOL

Just out of interest, how much slower is NFS than QS at 20 digits?

Quote:

Originally Posted by jasonp

I'll put in logic that uses NFS for postprocessing even if the input is smaller than the bound.

Do you mean in version 1.40?

BTW, I assume the crossover point you mentioned is for GNFS numbers. It's SNFS numbers that I posted this thread about.

jasonp · 2008-12-07, 14:32

Yes, the crossover point assumes GNFS. A 100-digit SNFS job with a correctly sized polynomial is around 10x faster than using QS.

At the 20-digit size, the NFS code is all overhead. The 40-digit sample test in the GGNFS source takes something like 30 seconds, whereas QS finishes in milliseconds.

10metreh · 2008-12-07, 17:47

Quote:

Originally Posted by jasonp

Yes, the crossover point assumes GNFS. A 100-digit SNFS job with a correctly sized polynomial is around 10x faster than using QS.

I was testing GGNFS's speed on googol+13's C94 when I found that msieve switched to QS. I thought msieve would have a lower minimum on the postprocessing.

Will you update in the next version?

10metreh · 2008-12-14, 11:23

My question has still not had an answer...

jasonp · 2008-12-14, 15:53

The answer is yes, this change is trivial to make.

The next version could be out several months from now, though, which is why I wasn't in a hurry to answer.

10metreh · 2008-12-14, 16:23

Quote:

Originally Posted by jasonp

The answer is yes, this change is trivial to make.

The next version could be out several months from now, though, which is why I wasn't in a hurry to answer.

Argh, it looks like it'll be a long wait...

However, it's such an easy change to make that you should easily be able to do it now and then wait those few months for version 1.41.

henryzz · 2008-12-14, 17:43

Quote:

Originally Posted by 10metreh

Argh, it looks like it'll be a long wait...

However, it's such an easy change to make that you should easily be able to do it now and then wait those few months for version 1.41.

i have attached a modified version of msieve 1.36 that doesnt reject lower number sizes which i compiled a while back on my athlon 64

10metreh · 2008-12-14, 17:48

Quote:

Originally Posted by henryzz

msieve 1.36

Could we have a similar one for 1.39? The poly selection has changed, if I want to do a C96 GNFS, for example (that will probably crop up in my aliquot sequence).

Ther is also a cygwin dll needed.

henryzz · 2008-12-14, 18:00

Quote:

Originally Posted by 10metreh

Could we have a similar one for 1.39? The poly selection has changed, if I want to do a C96 GNFS, for example (that will probably crop up in my aliquot sequence).

Ther is also a cygwin dll needed.

i forgot about that
i will have a go at compiling it
i havent compiled anything like that on my newish pc so it might not be set up properly yet

i cant do anything about needing a couple of cygwin dlls to run it
you should be able to download them easily though

2008-12-06, 20:54	#1
10metreh Nov 2008 2·3³·43 Posts	Msieve NFS minimum size Why does msieve's NFS require the number to be at least 97 digits? SNFS is much faster than QS for lower levels than that. Even just postprocessing will switch to the quadratic sieve instead.

2008-12-07, 02:26	#2
jasonp Tribal Bullet Oct 2004 2×3×19×31 Posts	Reports from users (admittedly old now) put the crossover point between msieve's QS and the GGNFS tools at 94-100 digits. Admittedly this sucks if you are completing a <97 digit job started by GGNFS. I can make the limit smaller, but I've already had a case of a public project try to use msieve for 20-digit NFS for instructional purposes. I'll put in logic that uses NFS for postprocessing even if the input is smaller than the bound. Last fiddled with by jasonp on 2008-12-07 at 02:28

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Estimating minimum relations	bchaffin	Factoring	24	2012-03-24 18:37
What is minimum RAM needed for 6 Core CPU for P-1?	odin	Hardware	15	2010-04-18 14:22
Minimum/desired CPU specs for ECM factoring	Kaboom	PrimeNet	10	2009-04-17 14:58
Minimum primes of various forms database?	jasong	Information & Answers	1	2007-11-01 01:58
Minimum delay between server connections	vaughan	ElevenSmooth	5	2005-09-08 17:17

2008-12-07, 14:32	#4
jasonp Tribal Bullet Oct 2004 2·3·19·31 Posts	Yes, the crossover point assumes GNFS. A 100-digit SNFS job with a correctly sized polynomial is around 10x faster than using QS. At the 20-digit size, the NFS code is all overhead. The 40-digit sample test in the GGNFS source takes something like 30 seconds, whereas QS finishes in milliseconds.

2008-12-14, 11:23	#6
10metreh Nov 2008 4422₈ Posts	My question has still not had an answer...

2008-12-14, 15:53	#7
jasonp Tribal Bullet Oct 2004 DCE₁₆ Posts	The answer is yes, this change is trivial to make. The next version could be out several months from now, though, which is why I wasn't in a hurry to answer.