Algorithmic Number Theory -- Proceedings of ANTS-III
(June 21 -- 25, 1998, Portland, Oregon, USA),
J. Buhler (Ed.),
vol. 1423 of
Lecture Notes in Computer Science,
Springer-Verlag.
Abstract:
The Number Field
Sieve (NFS) is the asymptotically fastest factoring algorithm known. In the
last stage of the NFS, one has to compute a square root of a huge algebraic
number given as a product of hundreds of thousands of small ones. This
problem was not satisfactorily solved until the appearance of an algorithm by
Peter Montgomery. We present a variant of the algorithm and discuss its
complexity.