An Implementation of the Number Field Sieve

REFERENCES

• Adleman , L. M. “Factoring numbers using singular integers” . Proceedings 23rd Annual ACM Symposium on Theory of Computing . 1991 , New Orleans . pp. 64 – 71 . New York : ACM. . [Adleman 1991]
   Google Scholar
• Batut , C. , Bernardi , D. , Cohen , H. and Olivier , M. User's Guide to Pari-GP. [Batut et al. 1995], This manual is part of the program distribution, available by anonymous ftp from the host megrez.math. u-bordeaux.fr
   Google Scholar
• Buhler , J. P. , Lenstra , H. W. Jr. and Pomerance , C. “Factoring integers with the number field sieve” 50 – 94 . [Buhler et al. 1993], [Lenstra et al. 1993a]
   Google Scholar
• Buhler , J. P. , Montgomery , P. L. , Robson , R. and Ruby , R. 1994 . “Technical report implementing the number field sieve” Corwallis , OR : Oregon State University. . [Buhler et al. 1994]
   Google Scholar
• Cohen , H. 1993 . A Course in Computational Algebraic Number Theory Berlin : Springer. . [Cohen 1993]
   Google Scholar
• Coppersmith , D. 1993 . “Solving linear equations over GF(2): Block Lanczos algorithm” . Linear Algebra and its Applications , 192 : 33 – 60 . [Coppersmith 1993]
   Web of Science ®Google Scholar
• Couveignes , J.-M. “Computing a square root for the number field sieve” 95 – 102 . [Couveignes 1993], [Lenstra et al. 1993a]
   Google Scholar
• Frobenius , F. G. 1968 . “Über Beziehungen zwischen den Primidealen eines algebraischen Körpers und den Substitutionen seiner Gruppe”. ” . In Sitzungsberichte der Königlich Preußischen Akademie der Wissenschaften zu Berlin Vol. Band II , 689 – 703 . Berlin : Springer. . [Frobenius 1896], Reprinted in Gesammelte Abhandlungen
   Google Scholar
• Golliver , R. A. , Lenstra , A. K. and McCurley , K. S. 1994 . “Lattice sieving and trial division”. ” . In Algorithmic Number Theory Edited by: Adleman , L. M. and Huang , M.-D. 18 – 27 . Berlin : Springer. . [Golliver et al. 1994], Lecture Notes in Comp. Sci. 877
   Google Scholar
• Knuth , D. E. 1981 . The Art of Computer Programming, vol. 2: Seminumerical Algorithms, , 2nd ed. Reading , MA : Addison–Wesley. . [Knuth 1981], (or 3rd ed., 1997)
   Google Scholar
• LaMacchia , B. A. and Odlyzko , A. M. 1991 . “Solving large sparse linear systems over finite fields”. ” . In Advances in Cryptology: CRYPTO ′90 Edited by: Menezes , A. J. and Vanstone , S. A. 109 – 133 . Berlin : Springer. . [LaMacchia et al. 1991], Lecture Notes in Comp. Sci. 537
   Google Scholar
• Lang , S. 1970 . Algebraic Number Theory Reading , MA : Addison–Wesley. . [Lang 1970]
   Google Scholar
• Lenstra , A. K. and Lenstra , H. W. Jr. 1993 . The Development of the Number Field Sieve Berlin : Springer. . [Lenstra et al. 1993a], Lecture Notes in Math. 1554
   Google Scholar
• Lenstra , A. K. , Lenstra , H. W. Jr. and Lovász , L. 1982 . “Factoring polynomials with rational coefficients” . Mathematische Annalen , 261 : 515 – 534 . [Lenstra et al. 1982]
   Web of Science ®Google Scholar
• Lenstra , A. K. , Lenstra , H. W. Jr. , Manasse , M. S. and Pollard , J. M. “The number field sieve” 11 – 42 . [Lenstra et al. 1993b], in [Lenstra et al. 1993a]
   Google Scholar
• Lenstra , A. K. , Lenstra , H. W. Jr. , Manasse , M. S. and Pollard , J. M. 1993 . “The factorization of the ninth Fermat number” . Mathematics of Computation , 61 : 319 – 349 . [Lenstra et al. 1993c]
   Web of Science ®Google Scholar
• Peter Montgomery , L. 1994 . “Square roots of products of algebraic numbers”. ” . In Mathematics of Computation 1943–1993: A Half-Century of Computational Mathematics Edited by: Gautschi , Walter . 567 – 571 . Providence : American Math. Soc. . [Montgomery 1994], Proceedings of Symposia in Applied Mathematics, Long version to appear
   Google Scholar
• Peter Montgomery , L. 1995 . “A block Lanczos algorithm for finding dependencies over GF(2)”. ” . In Advances in Cryptology: Eurocrypt ′95 Edited by: Guillou , L. C. and Quisquater , J.-J. 106 – 120 . Berlin : Springer. . [Montgomery 1995], Lecture Notes in Comp. Sci. 921
   Google Scholar
• Neukirch , J. 1992 . Algebraische Zahlentheorie Berlin : Springer. . [Neukirch 1992]
   Google Scholar
• Pollard , J. M. “Factoring with cubic integers” 4 – 10 . [Pollard 1993a], in [Lenstra et al. 1993a]
   Google Scholar
• Pollard , J. M. “The lattice sieve” 43 – 49 . [Pollard 1993b], in [Lenstra et al. 1993a]
   Google Scholar
• Pomerance , C. 1985 . “The quadratic sieve factoring algorithm”. ” . In Advances in Cryptology: Eurocrypt ′84 Edited by: Beth , T. , Cot , N. and Ingemarsson , I. 169 – 182 . New York : Springer. . [Pomerance 1985], Lecture Notes in Comp. Sci. 209
   Google Scholar
• Riesel , H. 1985 . Prime Numbers and Computer Methods for Factorization Boston : Birkhäuser. . [Riesel 1985]
   Google Scholar
• Standish , T. A. 1980 . Data Structure Techniques Reading , MA : Addison–Wesley. . [Standish 1980]
   Google Scholar