Go Back > Factoring Projects > YAFU

Thread Tools
Old 2013-02-26, 01:32   #1
skan's Avatar
Apr 2012

2·47 Posts
Default 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?


Last fiddled with by skan on 2013-02-26 at 01:35
skan is offline   Reply With Quote
Old 2013-02-26, 01:35   #2
Basketry That Evening!
Dubslow's Avatar
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 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.
Dubslow is offline   Reply With Quote
Old 2013-02-26, 03:27   #3
bsquared's Avatar
Feb 2007

3·1,193 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.
bsquared is offline   Reply With Quote
Old 2013-02-26, 07:21   #4
debrouxl's Avatar
Sep 2009

11110100102 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.
debrouxl is offline   Reply With Quote
Old 2013-02-26, 12:02   #5
skan's Avatar
Apr 2012

2×47 Posts


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.
skan is offline   Reply With Quote
Old 2013-02-26, 12:16   #6
Just call me Henry
henryzz's Avatar
Sep 2007
Cambridge (GMT/BST)

22·33·5·11 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.
henryzz is offline   Reply With Quote
Old 2013-02-26, 13:57   #7
Tribal Bullet
jasonp's Avatar
Oct 2004

1101110101112 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
jasonp is offline   Reply With Quote

Thread Tools

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

All times are UTC. The time now is 00:50.

Wed Dec 8 00:50:39 UTC 2021 up 137 days, 19:19, 0 users, load averages: 1.13, 1.21, 1.57

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.