Re: Naive Square root algorithm for GNFS ?

From: Pubkeybreaker (Robert_silverman_at_raytheon.com)
Date: 03/29/05 

Date: 29 Mar 2005 11:08:38 -0800

Hi,

Why C++??? What's so special about it? It would not be my choice were
I to
re-write my code.

If you know that your domain is a UFD, then you can compute the units
and
generators of the ideals. This makes find the square root easy.

If not, then there is nothing better than Peter's techniques. It is
very helpful
to have an algebraic number theory library available. This cuts down
on
much of the work. Indeed, the CWI code uses Pari.

 You say you have implemented the algorithm. Which parts have you
done?
Have you implemented Brian Murphy's ideas for polynomial generation?
What
technique do you use to find the roots? Are you using line or lattice
sieving?
How do you filter the data? Build the matrix? Solve it?

I think that a full implementation involves too much code to write for
a Master's
thesis. Getting all the details right in just the siever is several
months of full time
work. I would be happy to write a letter to your advisor on this
point.

The CWI suite (a very fine piece of work!!!) was the joint effort of
several people.
It required a LOT of work. Indeed, my implementation still lacks the
square root
code, and while I have filter code, it is not nearly as good as the CWI
code. It uses
Intelligent Gaussian elim, rather than cliques. My block Lanczos code
is also about
20% slower than the CWI code. OTOH, my line siever is slightly faster,
and my
lattice siever is a lot faster. The current CWI suite represents
years of excellent work.
Trying to duplicate it for a Master's thesis would be too much work.
(IMO)

Bob Silverman