Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: JSH: Upside down situation
Replies: 66   Last Post: Mar 21, 2008 11:05 AM

 Messages: [ Previous | Next ]
 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
>

Date Subject Author
3/14/08 jstevh@gmail.com
3/14/08 mensanator
3/14/08 jstevh@gmail.com
3/14/08 drtek
3/14/08 Ryugyong Hotel
3/14/08 jstevh@gmail.com
3/15/08 drtek
3/15/08 mensanator
3/15/08 Jesse F. Hughes
3/15/08 Vend
3/15/08 jstevh@gmail.com
3/15/08 David Bernier
3/16/08 rossum
3/16/08 Michael Press
3/16/08 MTBrenneman@gmail.com
3/17/08 Michael Press
3/17/08 Michael Press
3/16/08 mensanator
3/17/08 MTBrenneman@gmail.com
3/17/08 Michael Press
3/18/08 Tim Little
3/17/08 MTBrenneman@gmail.com
3/18/08 Tim Little
3/20/08 Pubkeybreaker
3/17/08 Rotwang
3/17/08 Michael Press
3/17/08 drtek
3/18/08 rossum
3/18/08 Randy Poe
3/18/08 rossum
3/18/08 jstevh@gmail.com
3/19/08 Michael Press
3/18/08 mensanator
3/19/08 Tim Smith
3/20/08 Pubkeybreaker
3/16/08 jstevh@gmail.com
3/16/08 rossum
3/17/08 jstevh@gmail.com
3/17/08 Canaan Banana
3/17/08 MTBrenneman@gmail.com
3/17/08 Marshall
3/17/08 drtek
3/17/08 litsohate@yahoo.com
3/16/08 Vend
3/17/08 Rupert
3/17/08 rossum
3/18/08 jstevh@gmail.com
3/19/08 David Bernier
3/19/08 rossum
3/19/08 jstevh@gmail.com
3/19/08 Rotwang
3/19/08 rossum
3/19/08 jstevh@gmail.com
3/19/08 drtek
3/20/08 rossum
3/19/08 Pubkeybreaker
3/19/08 rossum
3/19/08 Phil Carmody
3/20/08 Pubkeybreaker
3/20/08 drtek
3/21/08 rossum
3/19/08 tinyurl.com/uh3t
3/21/08 jstevh@gmail.com
3/21/08 drtek