mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2010-09-20, 17:09   #1
patrickkonsor
 
Oct 2008

2×5 Posts
Default 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
patrickkonsor is offline   Reply With Quote
Old 2010-09-20, 17:21   #2
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

43·59 Posts
Default

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
firejuggler is offline   Reply With Quote
Old 2010-09-21, 12:22   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by patrickkonsor View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2010-09-21, 20:10   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

24·13·17 Posts
Default

Alex Kruppa's PhD dissertation dealt with this subject too, in the context of factoring integers with three factors in that range.
jasonp is offline   Reply With Quote
Old 2010-09-21, 20:53   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111011000012 Posts
Default

Quote:
Originally Posted by jasonp View Post
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?
CRGreathouse is offline   Reply With Quote
Old 2010-09-22, 02:21   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

24·13·17 Posts
Default

The ECM portion of his dissertation is here as a separate technical report.
jasonp is offline   Reply With Quote
Old 2010-09-24, 16:59   #7
patrickkonsor
 
Oct 2008

2·5 Posts
Default

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.
patrickkonsor is offline   Reply With Quote
Old 2010-09-24, 18:04   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

Quote:
Originally Posted by patrickkonsor View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2010-09-24, 18:20   #9
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

18EF16 Posts
Default

Quote:
Originally Posted by patrickkonsor View Post
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
fivemack is offline   Reply With Quote
Old 2010-09-24, 18:27   #10
patrickkonsor
 
Oct 2008

2×5 Posts
Default

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
patrickkonsor is offline   Reply With Quote
Old 2010-09-24, 19:11   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100100101011012 Posts
Default

libecm is not thread-safe/aware, though, ...as far as I've heard.
That may be your problem.
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Awfully small factors.... petrw1 Lone Mersenne Hunters 17 2009-11-20 03:40
optimal parameters for GMP-ECM , -oe+ , -I Walter Nissen GMP-ECM 16 2007-03-20 19:35
Small factors Kees PrimeNet 6 2006-11-16 00:12
"Optimal" parameters for ECM Jushi GMP-ECM 4 2006-05-17 11:32
Missed small factors 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

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.