NFS on smaller numbers?

skan · 2013-02-26, 01:32

How can I force Yafu to use NFS instead of SIQS even on smaller numbers? (without recompiling)
Just to test speed.
next time you upload the windows version, could you please lower that limit?

thanks

Dubslow · 2013-02-26, 01:35

"nfs(num)" as opposed to "factor(num)"?

There's a built in limit to Msieve at like 80 digits or something; it's not really possible to do NFS on anything smaller than that.

bsquared · 2013-02-26, 03:27

The built in limit in YAFU is 85 digits. For Win32 the crossover is probably around 100 digits. For sure it is more than 85 digits, so you should be able to run enough tests to see the speed crossover.

debrouxl · 2013-02-26, 07:21

skan, NFS on numbers shorter than 90 digits is definitely a waste of CPU power

I ran tune yesterday evening with yafu 1.34 on Core i7-2670QM running 64-bit Linux, which estimated the NFS / SIQS crossover at 98 digits - despite usage of 64-bit ggnfs sievers. The crossover is higher than with previous versions of yafu, in line with the announced recent improvements to the SIQS code.

skan · 2013-02-26, 12:02

Hi

I know that on numbers smaller than 90 digits NFS is not the faster but I just would like to try it for number of 60 digits. Just to play with.

henryzz · 2013-02-26, 12:16

SNFS can be useful around that range. I personally don't like the limit as it limits what experimentation you can do. Low digit s/gnfs can be good for experimentation.

jasonp · 2013-02-26, 13:57

Msieve's postprocessing will take a minimum of around 1 minute, for SNFS or GNFS. Nowadays in 1 minute YAFU can factor a 90-digit input using multiple threads.

The Msieve cutoff is 85 digits for NFS, but that's only a limitation in the polynomial selection. I suppose if your input has an obvious SNFS polynomial then you can do the sieving and then postprocess like normal. To quote another post:

Right now you can run NFS postprocessing on any size number, but modifying polynomial selection to handle numbers smaller than the current limit requires the ability to select degree 3 polynomials and to find GNFS polynomial selection parameters suitable for numbers smaller than the current limit. Both of those would take some time, and in the meantime you'd find that if it works at all then factoring, say, a 60 digit number will take maybe 30 seconds if you're lucky and it doesn't crash, whereas if it does crash then I'd have additional work to do. You know that QS is a better choice at that size (YAFU would finish a 60-digit job in maybe 1 second), so getting the same answer in a much longer time is not useful, especially compared to what I could be doing on the codebase in its place.

Note that the CADO tools can perform complete factorizations down to 60 digits.

2013-02-26, 01:32	#1
skan Apr 2012 2·47 Posts	NFS on smaller numbers? How can I force Yafu to use NFS instead of SIQS even on smaller numbers? (without recompiling) Just to test speed. next time you upload the windows version, could you please lower that limit? thanks Last fiddled with by skan on 2013-02-26 at 01:35

2013-02-26, 13:57	#7
jasonp Tribal Bullet Oct 2004 3²·5·79 Posts	Msieve's postprocessing will take a minimum of around 1 minute, for SNFS or GNFS. Nowadays in 1 minute YAFU can factor a 90-digit input using multiple threads. The Msieve cutoff is 85 digits for NFS, but that's only a limitation in the polynomial selection. I suppose if your input has an obvious SNFS polynomial then you can do the sieving and then postprocess like normal. To quote another post: Right now you can run NFS postprocessing on any size number, but modifying polynomial selection to handle numbers smaller than the current limit requires the ability to select degree 3 polynomials and to find GNFS polynomial selection parameters suitable for numbers smaller than the current limit. Both of those would take some time, and in the meantime you'd find that if it works at all then factoring, say, a 60 digit number will take maybe 30 seconds if you're lucky and it doesn't crash, whereas if it does crash then I'd have additional work to do. You know that QS is a better choice at that size (YAFU would finish a 60-digit job in maybe 1 second), so getting the same answer in a much longer time is not useful, especially compared to what I could be doing on the codebase in its place. Note that the CADO tools can perform complete factorizations down to 60 digits. Last fiddled with by jasonp on 2013-02-26 at 14:04

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Using 16e on smaller numbers	fivemack	Factoring	3	2017-09-19 08:52
Sequences with smaller cofactors	Mr. Odd	Aliquot Sequences	8	2010-12-01 17:12
Smaller filtering run oddity	10metreh	Msieve	17	2009-01-05 14:58
checking smaller number	fortega	Data	2	2005-06-16 22:48
Factoring Smaller Numbers	marc	Factoring	6	2004-10-09 14:17

2013-02-26, 01:35	#2
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 16065₈ Posts	"nfs(num)" as opposed to "factor(num)"? There's a built in limit to Msieve at like 80 digits or something; it's not really possible to do NFS on anything smaller than that.

2013-02-26, 03:27	#3
bsquared "Ben" Feb 2007 111010010101₂ Posts	The built in limit in YAFU is 85 digits. For Win32 the crossover is probably around 100 digits. For sure it is more than 85 digits, so you should be able to run enough tests to see the speed crossover.

2013-02-26, 07:21	#4
debrouxl Sep 2009 11×89 Posts	skan, NFS on numbers shorter than 90 digits is definitely a waste of CPU power I ran tune yesterday evening with yafu 1.34 on Core i7-2670QM running 64-bit Linux, which estimated the NFS / SIQS crossover at 98 digits - despite usage of 64-bit ggnfs sievers. The crossover is higher than with previous versions of yafu, in line with the announced recent improvements to the SIQS code.

2013-02-26, 12:02	#5
skan Apr 2012 1011110₂ Posts	Hi I know that on numbers smaller than 90 digits NFS is not the faster but I just would like to try it for number of 60 digits. Just to play with.

2013-02-26, 12:16	#6
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 6031₁₀ Posts	SNFS can be useful around that range. I personally don't like the limit as it limits what experimentation you can do. Low digit s/gnfs can be good for experimentation.