mersenneforum.org Optimal Parameters for Small Factors
 Register FAQ Search Today's Posts Mark Forums Read

 2010-09-20, 17:09 #1 patrickkonsor   Oct 2008 2×5 Posts Optimal Parameters for Small Factors Hello all, I was wondering if anyone has any suggestions for the optimal B1 parameter and number of curves to run when attempting to factor numbers where the factors are known to be in the 7-9 digit range. I'm doing some work on the quadratic sieve where I need to factor many numbers in the 50-100 bit range (16-31 digit range), but where I know that useful numbers will have factors of 7-9 digits, and if the number has any larger or smaller factors then it's useless and I don't need to know the factors. Thanks, Patrick Konsor
 2010-09-20, 17:21 #2 firejuggler     Apr 2010 Over the rainbow 43·59 Posts for the 7-9 digits range, a B1 of 100 would be enough, after 30 or so (and again each time you find a factor, ) get 50 at 11000. it should get rid of the factor up to 20 -25 digits. Last fiddled with by firejuggler on 2010-09-20 at 17:23
2010-09-21, 12:22   #3
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by patrickkonsor Hello all, I was wondering if anyone has any suggestions for the optimal B1 parameter and number of curves to run when attempting to factor numbers where the factors are known to be in the 7-9 digit range. I'm doing some work on the quadratic sieve where I need to factor many numbers in the 50-100 bit range (16-31 digit range), but where I know that useful numbers will have factors of 7-9 digits, and if the number has any larger or smaller factors then it's useless and I don't need to know the factors. Thanks, Patrick Konsor
Read my joint paper with Sam Wagstaff:
A Practical Analysis of ECM Mathematics of Computation

 2010-09-21, 20:10 #4 jasonp Tribal Bullet     Oct 2004 24·13·17 Posts Alex Kruppa's PhD dissertation dealt with this subject too, in the context of factoring integers with three factors in that range.
2010-09-21, 20:53   #5
CRGreathouse

Aug 2006

10111011000012 Posts

Quote:
 Originally Posted by jasonp Alex Kruppa's PhD dissertation dealt with this subject too, in the context of factoring integers with three factors in that range.
Is this online somewhere?

 2010-09-22, 02:21 #6 jasonp Tribal Bullet     Oct 2004 24·13·17 Posts The ECM portion of his dissertation is here as a separate technical report.
 2010-09-24, 16:59 #7 patrickkonsor   Oct 2008 2·5 Posts Thanks guys, that information is helpful. Does anyone happen to know if GMP-ECM is primarily limited by memory bandwidth? I've tried running 6 different process (on a 12 core machine) but the performance of each is 6 times worse than running just one process at a time.
2010-09-24, 18:04   #8
CRGreathouse

Aug 2006

32×5×7×19 Posts

Quote:
 Originally Posted by patrickkonsor Does anyone happen to know if GMP-ECM is primarily limited by memory bandwidth? I've tried running 6 different process (on a 12 core machine) but the performance of each is 6 times worse than running just one process at a time.
I found a ~5-10% slowdown running two copies on an i7 (4-core). I'm not sure if it's transfer-limited or not.

2010-09-24, 18:20   #9
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

18EF16 Posts

Quote:
 Originally Posted by patrickkonsor Thanks guys, that information is helpful. Does anyone happen to know if GMP-ECM is primarily limited by memory bandwidth? I've tried running 6 different process (on a 12 core machine) but the performance of each is 6 times worse than running just one process at a time.
It really oughtn't to be limited by memory bandwidth, and I've always found it scaling pretty much perfectly when I run eight processes on an 8-core. Are you running it on truly enormous numbers?

Tom

 2010-09-24, 18:27 #10 patrickkonsor   Oct 2008 2×5 Posts No, 16-31 digit numbers (with 7-9 digit factors). To be specific, I'm not running it from the command line, I'm making library calls from within my program, which needs to factor tons of numbers in that range. I'm trying to run some parameter sweeps by running many different processes (each with just one thread), but, as I said, if I run 6 processes then they all slow down by a factor of 6 (and I know that the ECM library calls are responsible for almost all of the slow down). If I just run two processes then there's a 30% slow down per process. The only performance factor I can think of that would slow it down in this way this is memory bandwidth. Perhaps there's some sort of ECM configurations or parameters that might help? Last fiddled with by patrickkonsor on 2010-09-24 at 18:42
 2010-09-24, 19:11 #11 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100100101011012 Posts libecm is not thread-safe/aware, though, ...as far as I've heard. That may be your problem.

 Similar Threads Thread Thread Starter Forum Replies Last Post petrw1 Lone Mersenne Hunters 17 2009-11-20 03:40 Walter Nissen GMP-ECM 16 2007-03-20 19:35 Kees PrimeNet 6 2006-11-16 00:12 Jushi GMP-ECM 4 2006-05-17 11:32 dswanson Data 63 2004-11-24 04:30

All times are UTC. The time now is 14:32.

Tue Apr 13 14:32:15 UTC 2021 up 5 days, 9:13, 1 user, load averages: 3.50, 3.11, 2.89

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.