| Автор | Elkenbracht-Huizing, Marije |
| Дата выпуска | 1996 |
| dc.description | The Number Field Sieve (NFS) is the asymptotically fastest known factoring algorithm for large integers. This article describes an implementation of the NFS, including the choice of two quadratic polynomials, both classical sieving and a special form of lattice sieving (line sieving), the block Lanczos method and a new square root algorithm. Finally some data on factorizations obtained with this implementation are listed, including the record factorization of 12<sup>151</sup> – 1. |
| Формат | application.pdf |
| Издатель | Taylor & Francis Group |
| Копирайт | Copyright Taylor and Francis Group, LLC |
| Тема | number field sieve |
| Тема | factorization |
| Название | An Implementation of the Number Field Sieve |
| Тип | research-article |
| DOI | 10.1080/10586458.1996.10504590 |
| Electronic ISSN | 1944-950X |
| Print ISSN | 1058-6458 |
| Журнал | Experimental Mathematics |
| Том | 5 |
| Первая страница | 231 |
| Последняя страница | 253 |
| Аффилиация | Elkenbracht-Huizing, Marije; CWI |
| Выпуск | 3 |
| Библиографическая ссылка | 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] |
| Библиографическая ссылка | 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 |
| Библиографическая ссылка | 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] |
| Библиографическая ссылка | 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] |
| Библиографическая ссылка | Cohen, H. 1993. A Course in Computational Algebraic Number Theory Berlin: Springer.. [Cohen 1993] |
| Библиографическая ссылка | Coppersmith, D. 1993. “Solving linear equations over GF(2): Block Lanczos algorithm”. Linear Algebra and its Applications, 192: 33–60. [Coppersmith 1993] |
| Библиографическая ссылка | Couveignes, J.-M. “Computing a square root for the number field sieve” 95–102. [Couveignes 1993], [Lenstra et al. 1993a] |
| Библиографическая ссылка | 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 |
| Библиографическая ссылка | 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 |
| Библиографическая ссылка | 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) |
| Библиографическая ссылка | 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 |
| Библиографическая ссылка | Lang, S. 1970. Algebraic Number Theory Reading, MA: Addison–Wesley.. [Lang 1970] |
| Библиографическая ссылка | 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 |
| Библиографическая ссылка | 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] |
| Библиографическая ссылка | 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] |
| Библиографическая ссылка | 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] |
| Библиографическая ссылка | 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 |
| Библиографическая ссылка | 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 |
| Библиографическая ссылка | Neukirch, J. 1992. Algebraische Zahlentheorie Berlin: Springer.. [Neukirch 1992] |
| Библиографическая ссылка | Pollard, J. M. “Factoring with cubic integers” 4–10. [Pollard 1993a], in [Lenstra et al. 1993a] |
| Библиографическая ссылка | Pollard, J. M. “The lattice sieve” 43–49. [Pollard 1993b], in [Lenstra et al. 1993a] |
| Библиографическая ссылка | 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 |
| Библиографическая ссылка | Riesel, H. 1985. Prime Numbers and Computer Methods for Factorization Boston: Birkhäuser.. [Riesel 1985] |
| Библиографическая ссылка | Standish, T. A. 1980. Data Structure Techniques Reading, MA: Addison–Wesley.. [Standish 1980] |
