Re: Surrogate factoring demonstrated

From: Will Twentyman (wtwentyman_at_read.my.sig)
Date: 02/25/05 

Date: Thu, 24 Feb 2005 22:19:09 -0500

jstevh@msn.com wrote:

> The algorithm is so simple that it's amazing how often it does work.

What other methods have you compared it with that makes it amazing?

>
> Given a target M, you pick a j, where I now recommend picking a j as
> close to M as you can where j is *odd*, as I am now thinking that's
> important, again.
>
> Once you've picked j, you find T, using
>
> T = M^2 - j^2
>
> and my recommendation is that T have 2, 3 and 5 as factors, and there's
> a theoretical reason but I'm keeping things simple here.
>
> Then you just iterate through integers f_1 and f_2 such that
>
> f_1 f_2 = T^6
>
> so you need to factor T, and you use that f_1 and f_2 in
>
> w_num = +/-(f_1 +/- f_2) - 2T^2 (2j^2 + T)
>
> and you take the gcd of w_num with M, and if it's not 1, then you're
> done.

That's far more useful for letting us make test programs and
benchmarking vs other methods.

With a little effort, it should be easy to make a benchmarking program
to compare success rates and time to factor.

>
> That is the full algorithm. I know it looks too simple to be worth
> anything, but if you try it, you will be amazed at the high factoring
> percentage--for small numbers i.e. under 40 bits.

Do you have any data on how it compares with other methods either speed
or success wise? 

-- 
Will Twentyman
email: wtwentyman at copper dot net

Relevant Pages

  • Re: Surrogate factoring demonstrated
    ... That's far more useful for letting us make test programs and ... it should be easy to make a benchmarking program ... to compare success rates and time to factor. ...
    (sci.math)
  • RE: Pystone benchmark: Win vs. Linux (again)
    ... benchmarking program. ... functionality available in Python. ... compare across machines, etc. ... it's also not designed for comparisons across machines. ...
    (comp.lang.python)