20050523, 15:03  #1 
3·2,729 Posts 
ECM parameters for RSA
hi,
I want to try my luck, and do a few ECM curves for RSA640. And yes, I know my chances are very small, but still I want to try. I don't care if you will call me crazy XD I must admit I have tried, but my knowledge of proper parameters was too small, and program hasn't finished even one curve after 300 hours on a decent computer. I must have overestimated B1, but factor is probably in 9598 digits range, and this was my first try... Code:
ecm5 v 2114100000000 < rsa640.txt GMPECM 5.0.3 [powered by GMP 4.1.2] [ECM] Input number is 31074182404900437213507500358885679300373460228427275457201619488232064405 180815045563468296717232867824379162728380334154710731085019195485290073377248227835257423 86454014691736602477652346609 (193 digits) Using MODMULN Using B1=2114100000000, B2=863509532853116032, polynomial Dickson(30), sigma=3526725177 a=6391751212614921733862438670168218239336228500362278454251487177171096748134059741652897 267826020464676264214477837579122961776642012244299664314429350117095850843933081412297886 16424162158564 starting point: x=194503724204334031181634537695452191590737589204718226785924281226164802 978066402686717716964267714686115634460580831481268465536788867041132557962993351022593812 9172831529640192366453652986766 Can we estimate also how much places after decimal point is my chance of finding a factor? :D Spider 
20050523, 15:25  #2 
Jul 2004
Potsdam, Germany
3×277 Posts 
I think your B1 value is quite in the right range, I've estimated 3e12 as a good value (based on an approx. average increase to *3.5 for every 5 more digits).
So yes, it will take long  a quick shot of mine would be 25.000 hours (almost 3 years) on a *very* decent computer system. But you won't be able to complete it, as I'm quite sure the system will run out of memory way before that... Assuming you would be able to do so, I guesstimate you needed ~10,000,000 curves of these to have a chance of 1exp(1) finding a factor (it might be higher, as both factor are there...). My recommendation: Abort your try, as this unfortunately won't have any merit. I think ECMing other numbers which probably have factors in the range upto 50 digits is much wiser... Last fiddled with by Mystwalker on 20050523 at 15:26 
20050523, 16:41  #3 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Assuming B2=10^5*B1, I get an optimum around B1=10^11. The expected number of curves to find a factor is then about 11*10^6, but since there are two of approximately equal size, the expected number of curves to find one of them is half that  "only" about 5*10^6.
You could also try a somewhat lower B1, say 10^10. This increases the expected time to find a factor about 1.5 fold, but at least you'll actually see a curve complete sometime. It's pointless, but hey, it's your cputime... Alex 
20050523, 17:06  #4  
Nov 2003
7460_{10} Posts 
Quote:
ADDRESS enough memory to allow step 2 to run. With B1 ~ 2 x 10^12, the per curve chance of succeeding is about 10^7. This B1 is suboptimal. The primes are exactly 320 bits each. There is no hope of succeeding. I have no benchmark data for B1 > 32 bits. I have no idea how long it would take. This is, IMO, a silly and pointless computation. You would be MUCH better off using the time for GNFS. 

20050523, 17:27  #5 
"Nancy"
Aug 2002
Alexandria
2467_{10} Posts 
>Are you using a 64bit machine? A 32 bit machine won't even be able to
>ADDRESS enough memory to allow step 2 to run. He could limit the degree of the polynomials and do more blocks accordingly. That'll hurt performance, but when someone is trying to factor large RSA keys with ECM, efficiency clearly isn't his central concern... Alex Last fiddled with by akruppa on 20050523 at 17:27 
20050524, 21:45  #6 
13DC_{16} Posts 
memory needed
How much memory is needed to process the all number, say in a 64bit system. 4GB? or much more?

20050525, 12:03  #7 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
There's no simple answer to that. The memory requirements depend entirely on how you choose the parameters, particularly B2 and the number of blocks.
My recommendation for factoring large RSA keys with ECM is: don't. It's a waste of time. Alex 
20060329, 22:45  #8 
Mar 2006
10_{8} Posts 
that's common knowledge. i wouldnt try anything larger than 67 or so digits with ECM

20060604, 21:27  #9  
Jul 2005
2^{3}×5 Posts 
Quote:
Ron 

20060604, 23:13  #10  
Aug 2002
Buenos Aires, Argentina
2^{3}·13^{2} Posts 
Quote:
I would be impressed if you can make that number of modular multiplications in only a millisecond. This is only for step 1. You also have to program step 2 in your FPGA. 

20060605, 00:28  #11  
Jul 2005
2^{3}×5 Posts 
Quote:
Quote:
Ron 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
YAFU cli parameters  VolMike  YAFU  8  20121003 14:18 
SNFS 200 parameters  JoeCrump  Factoring  3  20091206 14:50 
Quartic: Parameters  R.D. Silverman  Factoring  9  20090218 23:24 
C140 Parameters  Chris61  Factoring  13  20070423 09:56 
optimal parameters for GMPECM , oe+ , I  Walter Nissen  GMPECM  16  20070320 19:35 