mersenneforum.org ECM parameters for RSA
 Register FAQ Search Today's Posts Mark Forums Read

 2005-05-23, 15:03 #1 Spider   2,213 Posts ECM parameters for RSA hi, I want to try my luck, and do a few ECM curves for RSA-640. 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 95-98 digits range, and this was my first try... Code: ecm5 -v 2114100000000 < rsa640.txt GMP-ECM 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 Please, give me some clues what should be B1, B2 and sigma, that one curve can finish in a 50-100 hours... Can we estimate also how much places after decimal point is my chance of finding a factor? :D Spider
 2005-05-23, 15:25 #2 Mystwalker     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 1-exp(-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 2005-05-23 at 15:26
 2005-05-23, 16:41 #3 akruppa     "Nancy" Aug 2002 Alexandria 1001101000112 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 cpu-time... Alex
2005-05-23, 17:06   #4
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 Originally Posted by Spider hi, I want to try my luck, and do a few ECM curves for RSA-640. 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 95-98 digits range, and this was my first try... Code: ecm5 -v 2114100000000 < rsa640.txt GMP-ECM 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 Please, give me some clues what should be B1, B2 and sigma, that one curve can finish in a 50-100 hours... Can we estimate also how much places after decimal point is my chance of finding a factor? :D Spider
Are you using a 64-bit machine? A 32 bit machine won't even be able to
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 sub-optimal.

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.

 2005-05-23, 17:27 #5 akruppa     "Nancy" Aug 2002 Alexandria 246710 Posts >Are you using a 64-bit 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 2005-05-23 at 17:27
 2005-05-24, 21:45 #6 Jorge Coveiro   395610 Posts memory needed How much memory is needed to process the all number, say in a 64-bit system. 4GB? or much more?
 2005-05-25, 12:03 #7 akruppa     "Nancy" Aug 2002 Alexandria 1001101000112 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
 2006-03-29, 22:45 #8 hatu     Mar 2006 23 Posts that's common knowledge. i wouldnt try anything larger than 67 or so digits with ECM
2006-06-04, 21:27   #9
rdotson

Jul 2005

23×5 Posts

Quote:
 Originally Posted by akruppa ... the expected number of curves to find one of them is half that - "only" about 5*10^6
That's actually quite encouraging in my case because my hardware (FPGA) implementation of ECM using a 704 bit bus width should be able to generate and test an elliptic curve in less than a millisecond. That would lead me to believe it could yield a solution in a few days if I ever manage to fit it into a real FPGA. At present the design is too large to fit into any FPGA I can afford, so I can only test it with a Verilog simulator.

Ron

2006-06-04, 23:13   #10
alpertron

Aug 2002
Buenos Aires, Argentina

52B16 Posts

Quote:
 Originally Posted by rdotson That's actually quite encouraging in my case because my hardware (FPGA) implementation of ECM using a 704 bit bus width should be able to generate and test an elliptic curve in less than a millisecond.
The problem is that B1 = 1011 requires about this number of elliptic curve operations, or 1012 modular multiplications.

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.

2006-06-05, 00:28   #11
rdotson

Jul 2005

23×5 Posts

Quote:
 Originally Posted by alpertron I would be impressed if you can make that number of modular multiplications in only a millisecond.
A 704 bit modular multiplication requires at most 1408 clock cycles, which on a Spartan3E XC3S500E FPGA with a 50MHz clock, is about 28 microseconds.
Quote:
 Originally Posted by alpertron This is only for step 1. You also have to program step 2 in your FPGA.
I don't know what the "step 1" and "step 2" is that you and others refer to, but I assume it has something to do with GMP-ECM(?). My implementation of ECM is based on the description in Chapter 7 of the wonderful book "Prime Numbers: A Computational Perspective" by Richard Crandall and Carl Pomerance.

Ron

 Similar Threads Thread Thread Starter Forum Replies Last Post VolMike YAFU 8 2012-10-03 14:18 JoeCrump Factoring 3 2009-12-06 14:50 R.D. Silverman Factoring 9 2009-02-18 23:24 Chris61 Factoring 13 2007-04-23 09:56 Walter Nissen GMP-ECM 16 2007-03-20 19:35

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

Mon Sep 21 01:08:57 UTC 2020 up 10 days, 22:19, 0 users, load averages: 1.51, 1.43, 1.50