drtek
Posts:
286
Registered:
9/18/06


Re: JSH: Upside down situation
Posted:
Mar 17, 2008 6:13 PM


"rossum" <rossum48@coldmail.com> wrote in message news:mnkqt35mjkd5m2a5dq21j7c2pkbrj4s85t@4ax.com... > On Fri, 14 Mar 2008 17:06:50 0700 (PDT), JSH <jstevh@gmail.com> > wrote: > >>I am currently working on my own practical implementation of what I >>call surrogate factoring that follows from the latest theory, and it >>is pleasingly fast, while I still have to work at getting it to factor >>really big numbers to my satisfaction. Oh, my stated goal is the >>ability to factor an RSA encryption sized number in under 10 minutes >>on a standard desktop. > Have you actually calculated how fast your current method would be on > a 500 bit RSA number James? > > I posted some timings: > > Average timings over 200 numbers: > 20 bits: 2.265 mSec average per number. 0 misfactors. > 22 bits: 10.310 mSec average per number. 0 misfactors. > 24 bits: 12.345 mSec average per number. 0 misfactors. > 26 bits: 50.155 mSec average per number. 0 misfactors. > 28 bits: 294.765 mSec average per number. 0 misfactors. >
If you graph this and model it with b* a ^ (( Number of bits  J ) / 2) and minimize diferences;
the best values are b = 0.55 a = 8 J = 22
For the smallest RSA 100 bits the model gives 9.14E+34 mSec. for RSA 500 it gives 3.6E+215 mSec
With a few more points, 29 and 30 bit, we can make a more accurate prediction.
But it looks like
1/2 * 8 ^ ((#bits  22)/2)
or
1/2 * 8 ^ 39 mSec for 100 bit RSA
and
1/2 * 8 ^ 239 mSec for the 500 bit RSA
I will let the reader figure how many years this is as an exercise.
> We can use those timings to do a rough backofanenvelope calculation > of how long it would take to factor a 500 bit RSA number. > > Taking the first significant figure, a 20 bit number takes 2 mSec and > a 28 bit number takes 200 mSec. So an 8 bit increase in length > multiplies time by a factor of 100. > > For a 500 bit number we need an extra 472 bits on top of the 28 bits > we start from. 472 / 8 = 59, so we need to multiply our time by 100 ^ > 59. This gives 200 x 100 ^ 59 mSec, which equals: > > 2 x 10^117 seconds > > Now neither my code nor my processor are the fastest. Assume better > coding and a faster processor will give a speed up of a factor of > 1000. Also assume that we can set a million processors (or 250,000 > quad processors) working in parallel on one RSA number. That is a > total speed up of one billion times, a factor of 10^9. This reduces > the time to: > > 2 x 10^108 seconds. > > So how long is that? Divide by 60 x 60 x 24 x 365.25 to get the > number of years: > > 6.3 x 10^100 years > > That is a lot more than ten minutes James, if we take the age of the > universe as 15 x 10^9 years, then it is 4 x 10^90 times as long as the > age of the universe. > > You have a great deal more work to do on your method before RSA > numbers are in any danger. > > Your timings are no doubt different from mine. You can easily do the > same calculations with your own timings. > > rossum >

