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.independent

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 ]
mensanator

Posts: 5,039
Registered: 12/6/04
Re: JSH: Upside down situation
Posted: Mar 18, 2008 8:52 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Mar 18, 7:26 pm, JSH <jst...@gmail.com> wrote:
> On Mar 18, 6:23 am, Randy Poe <poespam-t...@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".

>
> > 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.
>
> >            - Randy
>
> And he found wrong.  I've talked about this before but unfortunately,
> again, the sci.math newsgroup gets an idea in its head and just runs
> wild with it despite repeated attempts at correcting the mis-
> information.
>
> rossum does not do the most important thing with this idea which is
> WHY I say it's a solution to the factoring problem, with is search for
> a key variable I call k, modulo p.  What he said was he tried that and
> he got "misfactors" so he quit and instead incremented k by 1.
>
> So he didn't do the theory, and his change would do, what?  GASP.
> It's make it appear to behave exponentially!!!
>
> And also I should remind that my code is faster than rossum as his
> goes off a cliff doing the 1 increment thing before 40 bits I think,
> while I can actually do 100 bits or more with small factors but don't
> see the point.
>
> His approach goes off a cliff early because there are roughly k
> searches incrementing by 1, where k is approximately sqrt(T/2),
> usually as it can be a bit smaller.
>
> So for a 40 bit number he has about a 20 bit search, while my code can
> factor a 40 bit number with 20 searches, though it doesn't always
> which is about me solving some problems.  So compare 20 bits for
> searching to 20, and understand the difference searching modulo p
> versus not.
>
> There are maybe a couple of practical problems to solve and surrogate
> factoring handles arbitrarily large composites nearly flatly, as p
> increases roughly as T increases, so they cancel each other out.
>
> Done rightly, the theory says it's a solution to the factoring
> problem.
>
> Done stupidly as rossum does it, you're going to have to count roughly
> sqrt(T/2), so you're done before 40 bits, like poor rossum with his
> coding attempt, unlike my code which can go wild in ranges his can't
> touch.
>
> But it doesn't do what I want so I'm still working at it.  And I do
> use a quirky approach as the code calls itself to factor surrogates
> and does multiple checks with surrogates where, um, you could do just
> one, but I like it!  It's mine, and the approach helps me solve some
> other problems...
>
> Oh, I'm around 40 bits now consistently.  So don't get too excited
> that the code can do 100 bits with small factors as I'm saying like
> primes under 1000 or so, which you may say, hey, a brute force can do
> that!  Yeah, but how do you know when brute force can do that?
>
> I'm in a position now to evaluate claims of using surrogate factoring
> with, oh wow!, my own code, and I'm the best in the world that's
> talking about it loud and proud like this.  Hmmm...I'm getting used to
> being the best in the world.
>
> If not, someone needs to challenge me with surrogate factoring code.


When are you going to send me your code?

I need to translate it to Python in order to challenge you.

> You will not beat me, or if you do, I still celebrate and say, hah.
>
> James Harris




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.