Re: Simple answer, surrogate factoring

jstevh_at_msn.com
Date: 03/05/05 

Date: 5 Mar 2005 04:25:51 -0800

jstevh@msn.com wrote:
> Tim Peters wrote:
> > [JSH]
> > [...]
> > > where f_1 f_2 = Tj^2, and you iterate through all possible
integer
> f_1
> > > and f_2, and take the gcd of Ax with M.
> > >
> > > If Ax has M as a factor, then you calculate that ratio of z to x.
> > >
> > > The numerator is just
> > >
> > > (+/-(f_1 - f_2) + 2j^2 +/- (f_1 + f_2))
> >
> > I couldn't follow the derivation, so will just ask: the redundant
> pair of
> > outermost parentheses here is surprising, so is this really what
you
> meant
> > to type?
> >
> > > while the denominator is
> > >
> > > 2M^2 - 2(+/-(f_1 - f_2) + 2j^2
>
> Sorry, should be
>
> 2M^2 - 2(+/-(f_1 - f_2) + 2j^2)
>
> >
> > This one is missing a right parenthesis; don't know whether
> >
> > 2M^2 - 2(+/-(f_1 - f_2)) + 2j^2
> >
> > or
> >
> > 2M^2 - 2(+/-(f_1 - f_2) + 2j^2)
> >
> > was intended.
> >
> > > and you divide out any factors in common between them, and then
> take
> > > the gcd of the denominator with M, and for at least one case for
> any
> > > non-zero j coprime to M, you will have a prime factor of M.
> > >
> > > The basic algorithm is now perfect.
> >
> > I tried all plausible (to me) ways of fleshing out an
implementation
> from
> > this, and they all failed to factor some 3-digit composites.
> >
>
> Well, the proof is actually not hard, and it is perfect, so that
means
> in this case I can say definitely that you made some mistake.
>

Nope. I made a mistake.

It turns out that my "perfect" argument is no proof at all!!!

However, there's a silver lining, and thanks to Peters as considering
his posts here has helped me greatly.

I do apologize to him for questioning his methodology.

I just screwed up again, but I noticed something interesting...

James Harris

Relevant Pages

  • Re: Simple answer, surrogate factoring
    ... > Tim Peters wrote: ... >> outermost parentheses here is surprising, ... > in this case I can say definitely that you made some mistake. ...
    (sci.math)
  • Re: JSH: Hyperbolic factoring method
    ... Tim Peters wrote: ... Was there a reason people ... to push this that you are doing so with your eyes wide open. ... Make no mistake. ...
    (sci.crypt)