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 back-of-an-envelope 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
>
|
|
