Computation Of The Algebraic Square Root For The Number Field Sieve

The number field sieve (NFS) is the asymptotically fastest factoring method known. The computation of the square root of a huge algebraic number is the last stage of the N7FS. Several methods to solve this problem appeared since the NFS was first introduced in 1988 by Pollard. We selected the best one Montgomery- Nyugen method from them, and applied it successfully in factoring the RSA- 155. In this paper, we introduce Montgomery-Nyugen method in detail, and present several important aspects of our implementation.