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

Re: Sieve

Expand Messages
  • 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 1 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 2 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.