Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
drtek

Posts: 286
Registered: 9/18/06
Re: JSH: Upside down situation
Posted: Mar 17, 2008 6:13 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


"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
Read JSH: Upside down situation
jstevh@gmail.com
3/14/08
Read Re: JSH: Upside down situation
mensanator
3/14/08
Read Re: JSH: Upside down situation
jstevh@gmail.com
3/14/08
Read Re: JSH: Upside down situation
drtek
3/14/08
Read Re: Upside down situation
Ryugyong Hotel
3/14/08
Read Re: JSH: Upside down situation
jstevh@gmail.com
3/15/08
Read Re: JSH: Upside down situation
drtek
3/15/08
Read Re: JSH: Upside down situation
mensanator
3/15/08
Read Re: JSH: Upside down situation
Jesse F. Hughes
3/15/08
Read Re: JSH: Upside down situation
Vend
3/15/08
Read Re: JSH: Upside down situation
jstevh@gmail.com
3/15/08
Read Re: JSH: Upside down situation
David Bernier
3/16/08
Read Re: JSH: Upside down situation
rossum
3/16/08
Read Re: JSH: Upside down situation
Michael Press
3/16/08
Read Re: JSH: Upside down situation
MTBrenneman@gmail.com
3/16/08
Read Re: JSH: Upside down situation
Archie Nomad
3/17/08
Read Re: JSH: Upside down situation
Michael Press
3/17/08
Read Re: JSH: Upside down situation
Archie Nomad
3/17/08
Read Re: JSH: Upside down situation
Michael Press
3/16/08
Read Re: JSH: Upside down situation
mensanator
3/16/08
Read Re: JSH: Upside down situation
Archie Nomad
3/17/08
Read Re: JSH: Upside down situation
MTBrenneman@gmail.com
3/17/08
Read Re: JSH: Upside down situation
Michael Press
3/18/08
Read Re: JSH: Upside down situation
Tim Little
3/17/08
Read Re: JSH: Upside down situation
MTBrenneman@gmail.com
3/18/08
Read Re: JSH: Upside down situation
Tim Little
3/20/08
Read Re: JSH: Upside down situation
Pubkeybreaker
3/17/08
Read Re: JSH: Upside down situation
Rotwang
3/17/08
Read Re: JSH: Upside down situation
Michael Press
3/17/08
Read Re: JSH: Upside down situation
drtek
3/18/08
Read Re: JSH: Upside down situation
rossum
3/18/08
Read Re: JSH: Upside down situation
Randy Poe
3/18/08
Read Re: JSH: Upside down situation
rossum
3/18/08
Read Re: JSH: Upside down situation
jstevh@gmail.com
3/19/08
Read Re: JSH: Upside down situation
Michael Press
3/18/08
Read Re: JSH: Upside down situation
mensanator
3/19/08
Read Re: JSH: Upside down situation
Tim Smith
3/20/08
Read Re: JSH: Upside down situation
Pubkeybreaker
3/16/08
Read Re: JSH: Upside down situation
jstevh@gmail.com
3/16/08
Read Re: JSH: Upside down situation
rossum
3/17/08
Read Re: JSH: Upside down situation
jstevh@gmail.com
3/17/08
Read Re: JSH: Upside down situation
Canaan Banana
3/17/08
Read Re: JSH: Upside down situation
MTBrenneman@gmail.com
3/17/08
Read Re: JSH: Upside down situation
Marshall
3/17/08
Read Re: JSH: Upside down situation
drtek
3/17/08
Read Re: JSH: Upside down situation
litsohate@yahoo.com
3/16/08
Read Re: JSH: Upside down situation
Vend
3/17/08
Read Re: JSH: Upside down situation
Rupert
3/17/08
Read Re: JSH: Upside down situation
rossum
3/18/08
Read Re: JSH: Upside down situation
jstevh@gmail.com
3/19/08
Read Re: JSH: Upside down situation
David Bernier
3/19/08
Read Re: JSH: Upside down situation
rossum
3/19/08
Read Re: JSH: Upside down situation
jstevh@gmail.com
3/19/08
Read Re: JSH: Upside down situation
Rotwang
3/19/08
Read Re: JSH: Upside down situation
rossum
3/19/08
Read Re: JSH: Upside down situation
jstevh@gmail.com
3/19/08
Read Re: JSH: Upside down situation
drtek
3/20/08
Read Re: JSH: Upside down situation
rossum
3/19/08
Read Re: JSH: Upside down situation
Pubkeybreaker
3/19/08
Read Re: JSH: Upside down situation
rossum
3/19/08
Read Re: JSH: Upside down situation
Phil Carmody
3/20/08
Read Re: JSH: Upside down situation
Pubkeybreaker
3/20/08
Read Re: JSH: Upside down situation
drtek
3/21/08
Read Re: JSH: Upside down situation
rossum
3/19/08
Read Re: JSH: Upside down situation
tinyurl.com/uh3t
3/21/08
Read Re: JSH: Upside down situation
jstevh@gmail.com
3/21/08
Read Re: JSH: Upside down situation
drtek

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.