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

Factoring 12 digit numbers.

Expand Messages
  • Kermit Rose
    I applied one of the principles of the quadratic sieve ( without using the sieve part ) to extend the Fermat difference of squares method to factor larger
    Message 1 of 1 , Jan 31, 2008
    • 0 Attachment
      I applied one of the principles of the quadratic sieve ( without using
      the sieve part )
      to extend the Fermat difference of squares method to factor larger
      numbers more quickly than
      would the usual Fermat method.

      Here is an example number that would not have easily been factored by
      trial division.

      Probably it would also yield quickly to other well known algorithms, but
      I've not tested that.

      My algorithm is a strictly deterministic algorithm.

      Let r = int(sqrt(z))

      We search for t such that t squared = s squared with t not equal to s or
      -s mod z.

      Start at t = r + 1.

      Calculate in mod z, t**2, t**4, t**8, t**16, etc until the exponent is
      largest power of 2 < z,
      or until an integer square is found, or until the series begins to repeat.

      If no integer square is found then multiply the non-squares two at a
      time to search for a square product.

      If not successful, multiply the non-squares three at a time to search
      for a square product.

      If not successful, multiply the non-squares four at a time to search for
      a square product.



      >>> ExtendedFermat(products12[1])

      Factoring 519240287353L
      >>>

      Found Factors by four way product of power squares. steps = 2350 r
      = 720583 t = 720586 t - r = 3
      [800231L, 648863L]
      >>>



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