mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-05-23, 15:03   #1
Spider
 

2,213 Posts
Talking 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
  Reply With Quote
Old 2005-05-23, 15:25   #2
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3·277 Posts
Default

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
Mystwalker is offline   Reply With Quote
Old 2005-05-23, 16:41   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-05-23, 17:06   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-05-23, 17:27   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

>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
akruppa is offline   Reply With Quote
Old 2005-05-24, 21:45   #6
Jorge Coveiro
 

395610 Posts
Default memory needed

How much memory is needed to process the all number, say in a 64-bit system. 4GB? or much more?
  Reply With Quote
Old 2005-05-25, 12:03   #7
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2006-03-29, 22:45   #8
hatu
 
hatu's Avatar
 
Mar 2006

23 Posts
Default

that's common knowledge. i wouldnt try anything larger than 67 or so digits with ECM
hatu is offline   Reply With Quote
Old 2006-06-04, 21:27   #9
rdotson
 
rdotson's Avatar
 
Jul 2005

23×5 Posts
Default

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
rdotson is offline   Reply With Quote
Old 2006-06-04, 23:13   #10
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

52B16 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2006-06-05, 00:28   #11
rdotson
 
rdotson's Avatar
 
Jul 2005

23×5 Posts
Default

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
rdotson is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
YAFU cli parameters VolMike YAFU 8 2012-10-03 14:18
SNFS 200 parameters JoeCrump Factoring 3 2009-12-06 14:50
Quartic: Parameters R.D. Silverman Factoring 9 2009-02-18 23:24
C140 Parameters Chris61 Factoring 13 2007-04-23 09:56
optimal parameters for GMP-ECM , -oe+ , -I 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.