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...

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

[Mystwalker]

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...

[akruppa]

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

[R.D. Silverman]

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...

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.

[akruppa]

>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

How much memory is needed to process the all number, say in a 64-bit system. 4GB? or much more?

[akruppa]

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

[hatu]

that's common knowledge. i wouldnt try anything larger than 67 or so digits with ECM

[rdotson]

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

[alpertron]

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 = 10¹¹ requires about this number of elliptic curve operations, or 10¹² 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.

[rdotson]

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.

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