Re: SF: Back to theory

From: J (Jaybirdmac_at_yahoo.com)
Date: 02/25/05 

Date: 24 Feb 2005 21:49:48 -0800

Wouldn't the Strong Law of Small Numbers apply here? Try factoring
47143269.

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: 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: 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: SF: Back to theory
    ... Nora Baron wrote: ... Try factoring ... > That is not so much a law, I think, as a rule of thumb. ... > At this point you go through a lot of j's before you hit the ...
    (sci.math)
  • Re: simplify
    ... I need some guide on what to think about in-order to simplify this ... if I were to multiply all the denominator to go the lowest common ... If you find the correct LCD, it will get very simple very quickly. ... there are a number of factoring methods. ...
    (sci.math)