Loading ...
Sorry, an error occurred while loading the content.

trial division by addition

Expand Messages
  • aldrich617
    This type of division runs much faster than the usual method and may have made it a contender in 1993 for the swiftest factoring method widely available. To
    Message 1 of 3 , May 4, 2007
    • 0 Attachment
      This type of division runs much faster than the usual method
      and may have made it a contender in 1993 for the swiftest
      factoring method widely available.

      To illustrate:

      Starting with N = 1372864271 find the smallest 48 number pairs
      (a,b) such (N - a*b) mod 210 = 0. These are the starting points
      for the rest of the calculations.

      Suppose you have come upon (41,61). Take the sqrt(N)/210 = 176,
      then find 176 * 210 + 41 = 37001 and 177 * 210 + 61 = 37231.
      Next find N - 37001 * 37231 = -2246.

      Let X = 37001, Y = 37231, Z = -2246.
      The main loop of the method will be:

      Repeat
      Repeat
      y := y + 210;
      z := Z + X;
      Until Z >= 0;
      X := X - 210;
      Z := Z - y;
      Until Z <= 0;

      Z = 0 at X = 20411, y = 67261 and X * Y = N.
    • Phil Carmody
      ... Probably not. ... Come upon ? ... That is not the main loop, the main loop would contain the procedure by which you come upon the pair (41,61), and
      Message 2 of 3 , May 4, 2007
      • 0 Attachment
        --- aldrich617 <aldrich617@...> wrote:
        > This type of division runs much faster than the usual method
        > and may have made it a contender in 1993 for the swiftest
        > factoring method widely available.

        Probably not.

        > To illustrate:
        >
        > Starting with N = 1372864271 find the smallest 48 number pairs
        > (a,b) such (N - a*b) mod 210 = 0. These are the starting points
        > for the rest of the calculations.
        >
        > Suppose you have come upon (41,61).

        'Come upon'?

        > Take the sqrt(N)/210 = 176,
        > then find 176 * 210 + 41 = 37001 and 177 * 210 + 61 = 37231.
        > Next find N - 37001 * 37231 = -2246.
        >
        > Let X = 37001, Y = 37231, Z = -2246.
        > The main loop of the method will be:
        >
        > Repeat
        > Repeat
        > y := y + 210;
        > z := Z + X;
        > Until Z >= 0;
        > X := X - 210;
        > Z := Z - y;
        > Until Z <= 0;

        That is not the main loop, the main loop would contain the procedure by which
        you 'come upon' the pair (41,61), and would run what you have got there up to
        48 times for each of the pairs that it 'comes upon'.

        Here's a faster method to factor 1372864271:

        First, come upon the value 20411.
        Then perform the following
        if(1372864271%20411==0) { output(20411," ",1372864271/20411); }
        else { output("FLT is false"); }

        Phil

        () ASCII ribbon campaign () Hopeless ribbon campaign
        /\ against HTML mail /\ against gratuitous bloodshed

        [stolen with permission from Daniel B. Cristofani]

        __________________________________________________
        Do You Yahoo!?
        Tired of spam? Yahoo! Mail has the best spam protection around
        http://mail.yahoo.com
      • Jack Brennen
        ... 1993, widely available ? I m looking at my copy of Riesel s Prime Numbers and Computer Methods for Factorization -- I have the second edition, which was
        Message 3 of 3 , May 4, 2007
        • 0 Attachment
          aldrich617 wrote:
          > This type of division runs much faster than the usual method
          > and may have made it a contender in 1993 for the swiftest
          > factoring method widely available.
          >

          1993, "widely available"?

          I'm looking at my copy of Riesel's "Prime Numbers and Computer
          Methods for Factorization" -- I have the second edition, which
          was published in 1994.

          It discusses a bunch of methods which are generally much
          faster than the method you mention. Pollard's rho algorithm
          comes to mind as one which is *easier to implement* than the
          method you describe, probably faster 99% of the time, and
          which was invented in 1975. Brent's variant which improved
          the performance was published in 1980.

          Your number factors on my laptop in about 2 milliseconds using
          the example implementation of Brent's variant which comes with
          PARI/GP.

          Jack
        Your message has been successfully submitted and would be delivered to recipients shortly.