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

Comparison of factor routines.

Expand Messages
  • Kermit Rose
    I m comparing the time of three different algorithms. FactorBrent is the polynomial recursion algorithm x = x**2 + 1 mod z Factor T is my variation of the
    Message 1 of 1 , Dec 26, 2008
    • 0 Attachment
      I'm comparing the time of three different algorithms.

      FactorBrent is the polynomial recursion algorithm

      x = x**2 + 1 mod z

      Factor T is my variation of the Fermat difference of squares algorithm.

      Factor Fermat is the classical Fermat difference of squares algorithm.

      I find it interesting that comparison of these two examples suggest that
      if the two factors are sufficiently close together, then the classic
      Fermat difference of squares
      algorithm is faster than my variation.

      If the two factors are far apart, then my variation seems to be the
      faster of the two.

      Of course the Brent polynomial recursion algorithm is much much faster
      than either of the others.

      z = 5673678604496447 = 70907371L * 80015357L
      Time taken to factor by

      FactorBrent: 0.483999967575 seconds.
      FactorT: 15.7090001106 seconds.
      FactorFermat: 6.20899987221 seconds.


      z = 1233711939594151 = 16870433L * 73128647L

      Time taken to factor by

      FactorBrent: 0.483000040054 seconds.
      FactorT: 41.9019999504 seconds.
      FactorFermat: 490.794999838 seconds.

      My variation of the Fermat difference of squares is that
      instead of locating the potential t values in

      t**2 - s**2 = z, by repetitively adding 2,

      I generate the t values by Chinese remainder theorem
      applied to

      the solutions for t mod 3, t mod 5, t mod 7, etc, until the correct
      value for t is found.


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