- 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.
--- In email@example.com, "dleclair55" <dleclair55@y...>
> > 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
> varies depends on whether you are using the simple quadratic sieve,Tomabechi
> 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
> (http://www.asahi-net.or.jp/~KC2H-MSM/cn/index.htm) and try it outon
> 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
> I'll definitely do that, only thing is how much changesI only have the second edition so I can't really say.
> 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.
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:
And Eric Landquist's paper on QS:
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