Use Msieve NFS for small numbers?

skan · 2013-02-26, 01:37

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

jasonp · 2013-02-26, 12:41

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.

skan · 2013-02-26, 12:58

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

chris2be8 · 2013-02-26, 17:38

That's an easy SNFS target. Set up a file called test.poly containing:

Code:

n:115792089237316195423570985008687907853269984665640564039457584007913129639937
m: 18446744073709551616
c4: 1
c0: 1

And it should split quite fast if you point factMsieve.pl or factmsieve.py at it.

SNFS can beat QS at this size range if you can find a good enough poly.

Chris

bsquared · 2013-02-26, 17:42

Quote:

Originally Posted by chris2be8

SNFS can beat QS at this size range if you can find a good enough poly.

Chris

I don't have factmsieve.py set up right now to compare... but here's a target time:

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 ctrl-c 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

Dubslow · 2013-02-26, 17:54

What cpu is that? Using 8 threads of my 2600 I get 14 seconds...

bsquared · 2013-02-26, 18:30

It is:

Code:

detected        Intel(R) Xeon(R) CPU E5-4650 0 @ 2.70GHz

but the timing is kinda misleading because there are 4 of these cpu's in the system. When the threads can be spread out over multiple cpus then there isn't as much of a memory bandwidth bottleneck. If I force it to use one node (8 cores) with numactl then I get 11.8 seconds.

Batalov · 2013-02-26, 19:19

Nice servers at Mayo detected!

bsquared · 2013-02-26, 20:35

Quote:

Originally Posted by Batalov

Nice servers at Mayo detected!

Just too bad that I have to share it...

2013-02-26, 01:37	#1
skan 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

2013-02-26, 12:58	#3
skan Apr 2012 136₈ 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 2013-02-26 at 13:06

2013-02-26, 17:38	#4
chris2be8 Sep 2009 912₁₆ Posts	That's an easy SNFS target. Set up a file called test.poly containing: Code: n:115792089237316195423570985008687907853269984665640564039457584007913129639937 m: 18446744073709551616 c4: 1 c0: 1 And it should split quite fast if you point factMsieve.pl or factmsieve.py at it. SNFS can beat QS at this size range if you can find a good enough poly. Chris

2013-02-26, 18:30	#7
bsquared "Ben" Feb 2007 3,617 Posts	It is: Code: detected Intel(R) Xeon(R) CPU E5-4650 0 @ 2.70GHz but the timing is kinda misleading because there are 4 of these cpu's in the system. When the threads can be spread out over multiple cpus then there isn't as much of a memory bandwidth bottleneck. If I force it to use one node (8 cores) with numactl then I get 11.8 seconds.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
ECM on small Mersenne Numbers	Erich	PrimeNet	16	2012-09-29 23:08
P-1 on small numbers	Unregistered	Information & Answers	2	2011-08-22 22:53
Strong Law of Small Numbers?	Christenson	Information & Answers	36	2011-02-16 04:29
ECM on small Generalised Fermat numbers	geoff	Factoring	23	2010-09-13 23:50
A new Strong Law of Small Numbers example	cheesehead	Math	7	2009-02-06 20:49

2013-02-26, 12:41	#2
jasonp Tribal Bullet Oct 2004 5×709 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 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, 17:54	#6
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 1C35₁₆ Posts	What cpu is that? Using 8 threads of my 2600 I get 14 seconds...

2013-02-26, 19:19	#8
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23135₈ Posts	Nice servers at Mayo detected!