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

Using small moduli to filter in Fermat factoring

Expand Messages
  • Kermit Rose
    Hello everyone Over a year an a half ago I wondered how much improvement I could make on Fermat factoring, by using mod 8, 3, 5, 7, etc for more quickly
    Message 1 of 2 , Nov 10, 2006
    • 0 Attachment
      Hello everyone

      Over a year an a half ago I wondered how much improvement I could make
      on Fermat factoring,
      by using mod 8, 3, 5, 7, etc

      for more quickly finding difference of squares equal to the number to
      be factored.

      Finally the algorithm for doing it came to me. I've written tentative
      code, but it still has a bug in it.

      In spite of this bug, I now realize that the screening by small modulii
      does not help significantly.


      To illustrate the process,

      Suppose z = t^2 - s^2 .


      If z = 1 mod 8, then t is in {1,3,5,7} mod 8 and s is in { 0,4} mod 8
      If z = 3 mod 8, then t is in {2,6} mod 8 and s is in {1,3,5,7} mod 8
      If z = 5 mod 8, then t is in {1,3,5,7} mod 8, and s is in {2,6} mod 8
      If z = 7 mod 8, then t is in {0,4} mod 8, and s is in {1,3,5,7} mod 8.


      If z = 1 mod 3, then t is in {1,2} mod 3 and s is in {0} mod 3
      If z = 2 mod 3, then t is in {0} mod 3 and s is in {1,2} mod 3

      If z = 1 mod 5, then t is in {0,1,4} mod 5 and s is in {0,2,3} mod 5
      If z = 2 mod 5, then t is in {1,4} mod 5 and s is in {2,3} mod 5
      If z = 3 mod 5, then t is in {2,3} mod 5 and s is in {1,4} mod 5
      If z = 4 mod 5, then t is in {0,2,3} mod 5 and s is in {0,1,4} mod 5.

      etc


      z = t^2 - s^2 .

      Given the number z to be factored, I found z mod p for each positive
      prime p < 10000,
      then made a bitmap table for permitted and nonpermitted values of t mod p,
      and made a bitmap table for permitted and nonpermitted values of s mod p.

      The calculation to make the 2 * 1229 bitmap tables took less than a minute.

      As a preliminary, I made 1229 mod square root tables for each prime
      modulus < 10000.

      The time of calculation of the square root tables is included in that
      "less than a minute" alluded to above.


      I tested out my tentative program code on a product of two five digit
      primes.

      I haven't tried to time this sieve program on t values and s values in
      comparison to other algorithms.

      I just wanted to confirm whether or not this method would be timewise
      exponential or sub exponential.

      I'm almost persuaded that this screening method must be exponential,
      and thus will not, in itself, provide
      rapid factoring of large numbers.

      This is in spite of using sieve methods for generating the mod sqrt
      tables, and for generating the
      bitmaps of permitted t values and permitted s values.

      Perhaps I could speed it up a little bit by being more clever in my
      sieve algorithms and in paying closer attention
      to when I'm doing the same calculation more than once.

      But, right now I don't feel it's worth effort to try.

      I should go back to the textbooks for more inspiration on some of the
      other factoring algorithms that have come to mind.

      Kermit < kermit@... >
    • Phil Carmody
      ... I remember doing the same. I was sitting at an HPUX workstation at Nokia, so I guess that was 6-7 years ago. ... It s a constant factor speedup. See the
      Message 2 of 2 , Nov 10, 2006
      • 0 Attachment
        --- Kermit Rose <kermit@...> wrote:
        > Hello everyone
        >
        > Over a year an a half ago I wondered how much improvement I could make
        > on Fermat factoring, by using mod 8, 3, 5, 7, etc
        > for more quickly finding difference of squares equal to the number to
        > be factored.

        I remember doing the same. I was sitting at an HPUX workstation at Nokia, so I
        guess that was 6-7 years ago.

        > Finally the algorithm for doing it came to me. I've written tentative
        > code, but it still has a bug in it.
        >
        > In spite of this bug, I now realize that the screening by small modulii
        > does not help significantly.

        ...

        > I should go back to the textbooks for more inspiration on some of the
        > other factoring algorithms that have come to mind.

        It's a constant factor speedup. See the 'Factoring with sieves' section in
        Knuth. Which is basically an accelerated Fermat. I'm convinced it's possible to
        implement faster than how Knuth suggests, but again, that would only be another
        small constant factor speedup.

        Phil

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

        [stolen with permission from Daniel B. Cristofani]



        ____________________________________________________________________________________
        Want to start your own business?
        Learn how on Yahoo! Small Business.
        http://smallbusiness.yahoo.com/r-index
      Your message has been successfully submitted and would be delivered to recipients shortly.