Re: SF: Back to theory

From: Nora Baron (norabaron_at_hotmail.com)
Date: 02/25/05 

Date: 25 Feb 2005 10:52:21 -0800

Nora Baron wrote:
> J wrote:
> > Wouldn't the Strong Law of Small Numbers apply here? Try factoring
> > 47143269.
> >
>
> J,
>
> That is not so much a law, I think, as a rule of thumb.
>
> One thing I should have pointed out regarding my variant
> of Harris's scheme: there is an easy proof that it is
> guaranteed to factor M. Harris has not succeeded in proving
> that for his version.
>
> It's also easier to program.
>
> So here's how it works with M = 47143269.
>
> Let j = 2: T = 47143267. Let f = 47143266, g = 1.
>

**** A misprint there - should have been f = 47143267, g = 1.

> Then X = (47143267 - 1)/(4713267 + 1). The numerator of
> X is 47143266, which has a factor of 3 in common with M.
> Thus replace M with M / 3 = 15714423.
>
> Now let j = 2 again, T = 15714421, f = 15714421, g = 1,
> X = 15714420 / 15714422. Again the numerator has a factor of
> 3 in common with 15714423. Thus let the new M = 15714423 / 3
> = 5238141.
>
> Continue one more step like this until you get to M = 1746047.
>
> At this point you go through a lot of j's before you hit the
> next factor. But when j = 348, T = M - j = 1746047 - 348 = 1745699.
> Letting f = 1745699, g = 1, the numerator of X is 1745698.
>
> As it happens, 1745698 has a factor of 349 (a prime) in common with
> M = 1746047. And 1746047 /349 = 5003, which is a prime. Therefore
> putting all this together, the factorization of the *original* M is
>
> M = 47143269 = 3^3 * 349 * 5003.
>
>
> Nora B.
>
>
> >
> > Nora Baron wrote:
> > > You have made this so much more complicated than it needs to
> > > be. Here is a simpler approach that may accomplish much the
> > > same and it is also much more general.
> > >
> > > Assume M is the number to be factored. Pick a (small)
> > > integer j. Let T = M - j. Thus T is a function of both
> > > M and j.
> > >
> > > Factor T. Assume you have split it into two factors,
> > > f and g. Thus T = f*g.
> > >
> > > Now let X be some rational function of f and g. One
> > > possible choice might be,
> > >
> > > X = (f - g)/(f + g).
> > >
> > > Finally, let Y = M / X. Thus M = X * Y.
> > >
> > > Note that X and Y are both functions of the factors of
> > > T. Also both are rational numbers. There is some chance
> > > that the numerator of X has a factor in common with M.
> > >
> > > This is, certainly, surrogate factoring. Really, your
> > > underlying idea is not that different. What you are doing
> > > essentially is finding a more complex function to define
> > > X as a function of f and g.
> > >
> > > Here is how this might work with M = 15. Let j = 1.
> > > Then T = M - j = 14. You factor T as f * g = 7 * 2. Then
> > > you note that
> > >
> > > X = (7 - 2) / (7 + 2) = 5/9.
> > >
> > > Right there, in the numerator, you have a factor that
> > > divides M.
> > >
> > > Interestingly, the denominator, 9, also has a factor in
> > > common with M.
> > >
> > > Let's try it on a bigger number. Say M = 77. This time let
> > > j = 2. T = 75 = 3* 5 * 5. Let f = 25 and g = 3. Then
> > >
> > > X = (f - g)/(f + g) = (25 - 3)/(25 + 3) = 22/28 = 11/14.
> > >
> > > Note that the numerator of X, namely 11, is a factor of 77.
> > > And again, the denominator, 14, also has a factor in common
> > > with 77.
> > >
> > > Pretty amazing, eh?
> > >
> > > I am a little surprised myself. I typed out this whole
> > > message in the last 15 minutes. I just made up the function
> > > that defines X, X = (f - g)/(f + g). I could have chosen an
> > > infinity of other functions. Also, quite honestly, I just
> > > made up the two examples. I must confess that I did try j = 1
> > > with the second example mentally, and saw it was not going
> > > to work, so I tried j = 2. No other trial-and-error.
> > >
> > > What's the point?
> > >
> > > The point is, I have modified and greatly simplified your
> > > central idea - and at the same time, greatly generalized it -
> > > and on these two simple little examples - the only ones
> > > I have tried - it works. It might work on lots of other
> > > examples. If it doesn't, I can try changing the function
> > > that defines X. I can add parameters, like your A, y, and z.
> > > Your central theme, surrogate factoring of the number
> > > T = M - j, is still there, and it might even explain why
> > > it works (if it does). After all, the factors of M ought
> > > to be related somehow to the factors of T. In the case of
> > > RSA numbers, in general you expect T to be easier to factor
> > > than M.
> > >
> > >
> > > Nora B.

Relevant Pages

  • Re: SF: Back to theory
    ... intelligent explanation of your factoring ... factoring method go through more or less j's to get to the factor 349? ... Nora Baron wrote: ... > That is not so much a law, I think, as a rule of thumb. ...
    (sci.math)
  • Re: JSH: Brainstorming over, for now
    ... [Nora Baron] ... I've just had a massive collapse in terms of getting surrogate ... That's from his "Big collapse on surrogate factoring" msg of March 10, ...
    (sci.math)
  • Re: SF: Two square, mystery celebration
    ... So now you're making up stuff in the factoring arena. ... You're just talking about freaking difference of squares and trying to ... Not very bright "Nora Baron" as there are too many people who care ... going to accept that some sci.math poster just showed them up by ...
    (sci.crypt)
  • Re: Factoring with cubic equations?
    ... Bob pretty much qualifies as an expert in the field of factoring as ... if we can find a representation ... > are you implying that we are missing what the essence of the factoring ... > it's like saying we have to prove the law of gravity at every point in this ...
    (sci.crypt)
  • Re: SF: Back to theory
    ... That is not so much a law, I think, as a rule of thumb. ... which has a factor of 3 in common with M. ... >> This is, certainly, surrogate factoring. ...
    (sci.math)
Loading