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

Re: Sieve

Expand Messages
  • dleclair55
    Hi, ... There are no hard and fast rules because the optimal factor base size varies depends on whether you are using the simple quadratic sieve, the multiple
    Message 1 of 4 , Oct 5, 2004
    • 0 Attachment
      Hi,

      > I'm (attempting) to make a quadratic and no resources
      > are making it clear on how I choose the size of the
      > factor base to use. Can anyone help me on how to do that?

      There are no hard and fast rules because the optimal factor base size
      varies depends on whether you are using the simple quadratic sieve,
      the multiple polynomial version, the self-initializing version and
      whether or not you are allowing zero, one, two or more large primes.

      My recommendation to you is to get a copy of "Prime Numbers and
      Computer Methods for Factorization" by Hans Riesel, published by
      Birkauser-Verlag. Try to get the second edition.

      It has a worked out example of the continued fraction method (CFRAC)
      which shares many properties with the quadratic sieve.

      If you really just want to know what size of factor base is used for
      numbers of various sizes, get the implementation of SIQS by Tomabechi
      (http://www.asahi-net.or.jp/~KC2H-MSM/cn/index.htm) and try it out on
      various candidates. But as I said above, the optimal size will vary
      depending on the variation you implement and to a certain degree on
      the efficiency of your implementation.

      -Don Leclair
    • plano9
      I ll definitely do that, only thing is how much changes in the second edition? Does the first edition include the CFRAC example? I need to decide if its
      Message 2 of 4 , Oct 5, 2004
      • 0 Attachment
        I'll definitely do that, only thing is how much changes in the second
        edition? Does the first edition include the CFRAC example? I need
        to decide if its worth the extra money to buy the second edition.

        Thanks,
        Plano9

        --- In primenumbers@yahoogroups.com, "dleclair55" <dleclair55@y...>
        wrote:
        >
        > Hi,
        >
        > > I'm (attempting) to make a quadratic and no resources
        > > are making it clear on how I choose the size of the
        > > factor base to use. Can anyone help me on how to do that?
        >
        > There are no hard and fast rules because the optimal factor base
        size
        > varies depends on whether you are using the simple quadratic sieve,
        > the multiple polynomial version, the self-initializing version and
        > whether or not you are allowing zero, one, two or more large primes.
        >
        > My recommendation to you is to get a copy of "Prime Numbers and
        > Computer Methods for Factorization" by Hans Riesel, published by
        > Birkauser-Verlag. Try to get the second edition.
        >
        > It has a worked out example of the continued fraction method (CFRAC)
        > which shares many properties with the quadratic sieve.
        >
        > If you really just want to know what size of factor base is used for
        > numbers of various sizes, get the implementation of SIQS by
        Tomabechi
        > (http://www.asahi-net.or.jp/~KC2H-MSM/cn/index.htm) and try it out
        on
        > various candidates. But as I said above, the optimal size will vary
        > depending on the variation you implement and to a certain degree on
        > the efficiency of your implementation.
        >
        > -Don Leclair
      • dleclair55
        Hi, ... I only have the second edition so I can t really say. On the subject of factoring I believe the second edition adds a more complete description of the
        Message 3 of 4 , Oct 5, 2004
        • 0 Attachment
          Hi,

          > I'll definitely do that, only thing is how much changes
          > in the second edition? Does the first edition include
          > the CFRAC example? I need to decide if its worth the
          > extra money to buy the second edition.

          I only have the second edition so I can't really say.

          On the subject of factoring I believe the second edition adds a more
          complete description of the number field sieve (but not up-to-date
          with current developments). But, to be honest, I'm not 100% sure what
          else is different.

          Another excellent and more recent book is "Prime Numbers: A
          Computational Perspective" by Richard Crandall and Carl Pomerance.

          It was Pomerance who first discovered the quadratic sieve and his book
          with Crandall is great reading but I found that Riesel's book offers a
          more detailed introduction to CFRAC and QS for the beginner. It was
          the book that first helped me to understand the mechanics of the QS.

          I can suggest a few more good references available online:

          Scott Contini's paper on SIQS is very good:
          http://www.crypto-world.com/documents/siqs.ps.gz

          And Eric Landquist's paper on QS:
          http://www.cs.virginia.edu/crab/QFS_Simple.pdf

          Implementing the quadratic sieve, especially if you do the filtering
          and linear algebra parts too, is a lot of work but it is extremely
          rewarding. I've managed to factor a 114-digit composite with my SIQS
          implementation, and not too far in the past that would have been
          somewhat impressive.

          -Don Leclair
        Your message has been successfully submitted and would be delivered to recipients shortly.