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

Why Fermat method of factoring is as fast as it is.

Expand Messages
  • Kermit Rose
    Consider factoring of 91 = 10^2 - 3^2 = (10 - 3) * (10 + 3) This took one step by Fermat method whereas the difference of the factors is 13 - 7 = 6. I wondered
    Message 1 of 1 , Nov 12, 2006
    • 0 Attachment
      Consider factoring of 91 = 10^2 - 3^2 = (10 - 3) * (10 + 3)

      This took one step by Fermat method whereas the difference of the
      factors is 13 - 7 = 6.

      I wondered why the Fermat method is actually much faster than
      proportional to the difference of the factors.

      Today I figured it out.

      Let z = x y = t^2 - s^2

      x = t - s; y = t + s; t = (y + x)/2 ; s = (y - x)/2

      Let A = integer part of sqrt of z.

      Assume z is not = to A^2 for otherwise the factoring is trivial.

      x < A < y

      Define f by

      f = [ (y - A) - (A - x) ] / 2 = ( y - A - A + x)/2 = (2 t - 2 A )/2
      = t - A

      t = f + A

      Note that f is defined to be half of the difference of the distance of
      A from y and distance of A from x.

      Since A is between x and y, f is significantly smaller than (y - x).

      Note also that f is in lockstep with t.

      z = t^2 - s^2 = (A + f)^2 - s^2 = A^2 + 2 f A + f^2 - s^2

      Thus s^2 = A^2 + 2 f A + f^2 - z

      Also
      z = A^2 + 2 f A - [ 2 f A + A^2 - z ], where [ 2 f A + A^2 - z] is the
      constant term.

      Consider z to be a quadratic in A

      A^2 + 2 f A - [2 f A + A^2 - z] factors as

      [ A - ( -f - sqrt[ f^2 + 2 f A+ A^2 - z ] ) ] ) ] [ A - ( - f +
      sqrt[ f^2 + 2 f A + A^2 - z ] )

      = [ A - (-f - s) ] [ A - ( -f + s ) ]

      = ( A + f - s) ( A+f - s)

      which we could have figured out more quickly by

      z = (t - s) * (t + s) = (A + f - s) * (A + f + s)


      Thus, the Fermat method is acutally progressing by incrementing f by 1
      , starting with f = 1, until f is half the difference
      of the distances of A from x and distance of y from A.

      This number , f, is significantly smaller than the distance (y - x).

      If we could make a better initial guess than sqrt(z) for the value of t
      = ( y + x) / 2, then we could find the factors more quickly.

      Knowing lower bounds for x or upper bounds for y would enable us to put
      stricter bounds on t.


      Kermit < kermit@... >
    Your message has been successfully submitted and would be delivered to recipients shortly.