- 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?

Thanks,

Plano9 - Hi,

> I'm (attempting) to make a quadratic and no resources

There are no hard and fast rules because the optimal factor base size

> 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?

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 - 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:>

size

> 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

> 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 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 - Hi,

> I'll definitely do that, only thing is how much changes

I 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:

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