mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

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

2×47 Posts
Default 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
skan is offline   Reply With Quote
Old 2013-02-26, 12:41   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

66378 Posts
Default

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

2·47 Posts
Default

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
skan is offline   Reply With Quote
Old 2013-02-26, 17:38   #4
chris2be8
 
chris2be8's Avatar
 
Sep 2009

3×72×13 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2013-02-26, 17:42   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1100110111102 Posts
Default

Quote:
Originally Posted by chris2be8 View Post

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

Last fiddled with by bsquared on 2013-02-26 at 17:43 Reason: trim quote
bsquared is offline   Reply With Quote
Old 2013-02-26, 17:54   #6
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·2,399 Posts
Default

What cpu is that? Using 8 threads of my 2600 I get 14 seconds...
Dubslow is offline   Reply With Quote
Old 2013-02-26, 18:30   #7
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×33×61 Posts
Default

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.
bsquared is offline   Reply With Quote
Old 2013-02-26, 19:19   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·3,041 Posts
Default

Nice servers at Mayo detected!
Batalov is offline   Reply With Quote
Old 2013-02-26, 20:35   #9
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1100110111102 Posts
Default

Quote:
Originally Posted by Batalov View Post
Nice servers at Mayo detected!


Just too bad that I have to share it...
bsquared is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 07:08.

Tue Oct 20 07:08:19 UTC 2020 up 40 days, 4:19, 0 users, load averages: 1.54, 1.63, 1.60

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.