rossum
Posts:
724
Registered:
12/13/04
|
|
Re: JSH: Upside down situation
Posted:
Mar 18, 2008 12:11 PM
|
|
On Tue, 18 Mar 2008 06:23:17 -0700 (PDT), Randy Poe
<poespam-trap@yahoo.com> wrote:
>On Mar 18, 5:04 am, rossum <rossu...@coldmail.com> wrote:
>> On Mon, 17 Mar 2008 17:13:54 -0500, "Jane Jian" <dd...@yahoo.com>
>> wrote:
>>
>>
>>
>>
>>
>> >"rossum" <rossu...@coldmail.com> wrote in message
>> >news:mnkqt35mjkd5m2a5dq21j7c2pkbrj4s85t@4ax.com...
>> >> On Fri, 14 Mar 2008 17:06:50 -0700 (PDT), JSH <jst...@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.
>>
>> Thanks for that. I was hoping that someone would do a proper
>> curve-fitting for the timings rather than the simple linear
>> extrapolation from the two extreme points that I did. In effect the
>> result is the same, James' method is an improvement on his normal
>> efforts but still has a long way to go if he wants to meet his goal of
>> factoring an RSA number in ten minutes.
>>
>> rossum
>
>Unfortunately, all James heard from this was
>"faster than... Fermat's". So now he is convinced that
>you have proven he's "solved the factoring problem".
James has been convinced he has solved the factoring problem for some
time. Praise confirms his conviction, criticism also confirms his
conviction since it shows that the maths establishment is getting
worried.
>
>He has totally missed the fact that:
> (a) factoring is difficult, not practically solvable
>for RSA numbers, because it scales exponentially, and
>
> (b) you found that the JSH "fast" method scales
>... wait for it...
>
>EXPONENTIALLY.
I am not at all sure that James has grasped the meaning of Big-O
notation in general and the meaning of "exponential" in particular.
It seems to me that it was only in the last year that he understood
that the essence of the factoring problem was not just to factor
numbers but to factor them quickly. I suspect that he still thinks
that "quickly" in this context is a simple matter of timing rather
than meaning "sub-exponential" in Big-O terms.
James, you could start by reading
http://en.wikipedia.org/wiki/Big_O_notation which gives an
introduction to the topic. Your method is exponental, O(c^n), where c
is a constant and n is the number of bits in the number you are
factoring. This is too slow to make an impact on RSA numbers. You
need a sub-exponential algorithm.
rossum
>
> - Randy
|
|
