Sieve

Expand Messages
• 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
Message 1 of 4 , Oct 5, 2004
• 0 Attachment
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, ... 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 2 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
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

-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
Message 3 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

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
> 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
• 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 4 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.