20130226, 01:37  #1 
Apr 2012
2×47 Posts 
Use Msieve NFS for small numbers?
How can I force Msieve to use NFS instead of SIQS even on smaller numbers? (without recompiling). Currently +80 digits.
Just to test speed. next time you upload the windows version, could you please lower that limit? thanks 
20130226, 12:41  #2 
Tribal Bullet
Oct 2004
6721_{8} Posts 
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 60digit 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. 
20130226, 12:58  #3 
Apr 2012
2·47 Posts 
Hi
I know that NFS is not as efficient as SIQS or ECM with small numbers, I just want to try it. The number I'm factorizing is 78 digits long. "2^(2^8)+1". I'm trying "msieve n .." but it runs siqs instead Last fiddled with by skan on 20130226 at 13:06 
20130226, 17:38  #4 
Sep 2009
2,039 Posts 
That's an easy SNFS target. Set up a file called test.poly containing:
Code:
n:115792089237316195423570985008687907853269984665640564039457584007913129639937 m: 18446744073709551616 c4: 1 c0: 1 SNFS can beat QS at this size range if you can find a good enough poly. Chris 
20130226, 17:42  #5  
"Ben"
Feb 2007
3433_{10} Posts 
Quote:
Code:
xxx.xxx.xxx 327 % yafu "siqs(2^(2^8)+1)" threads 8 starting SIQS on c78: 115792089237316195423570985008687907853269984665640564039457584007913129639937 ==== sieving in progress ( 8 threads): 37456 relations needed ==== ==== Press ctrlc to abort and save state ==== 39500 rels found: 21514 full + 17986 from 189784 partial, (23483.89 rels/sec) SIQS elapsed time = 10.6089 seconds. ***factors found*** P62 = 93461639715357977769163558199606896584051237541638188580280321 P16 = 1238926361552897 Last fiddled with by bsquared on 20130226 at 17:43 Reason: trim quote 

20130226, 17:54  #6 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
What cpu is that? Using 8 threads of my 2600 I get 14 seconds...

20130226, 18:30  #7 
"Ben"
Feb 2007
110101101001_{2} Posts 
It is:
Code:
detected Intel(R) Xeon(R) CPU E54650 0 @ 2.70GHz 
20130226, 19:19  #8 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
22310_{8} Posts 
Nice servers at Mayo detected!

20130226, 20:35  #9 
"Ben"
Feb 2007
3,433 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
ECM on small Mersenne Numbers  Erich  PrimeNet  16  20120929 23:08 
P1 on small numbers  Unregistered  Information & Answers  2  20110822 22:53 
Strong Law of Small Numbers?  Christenson  Information & Answers  36  20110216 04:29 
ECM on small Generalised Fermat numbers  geoff  Factoring  23  20100913 23:50 
A new Strong Law of Small Numbers example  cheesehead  Math  7  20090206 20:49 