A kilobit special number field sieve factorization. (English) Zbl 1153.11344
Kurosawa, Kaoru (ed.), Advances in cryptology – ASIACRYPT 2007. 13th international conference on the theory and application of cryptology and information security, Kuching, Malaysia, December 2-6, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-76899-9/pbk). Lecture Notes in Computer Science 4833, 1-12 (2007).
Summary: We describe how we reached a new factoring milestone by completing the first special number field sieve factorization of a number having more than 1024 bits, namely the Mersenne number \(2^{1039} - 1\). Although this factorization is orders of magnitude ‘easier’ than a factorization of a 1024-bit RSA modulus is believed to be, the methods we used to obtain our result shed new light on the feasibility of the latter computation.
For the entire collection see [Zbl 1135.94001].
For the entire collection see [Zbl 1135.94001].
MSC:
| 11Y05 | Factorization |
| 11T71 | Algebraic coding theory; cryptography (number-theoretic aspects) |
| 11Y16 | Number-theoretic algorithms; complexity |
| 94A60 | Cryptography |
References:
| [1] | Aoki, K., Kida, Y., Shimoyama, T., Ueda, H.: http://www.crypto-world.com/announcements/SNFS274.txt |
| [2] | Aoki, K., Shimoyama, T.: R311 is factored by ECM, Proceedings of SCIS 2004, no.2E1-1, Hiroshima, Japan, Technical Group on Information Security (IEICE) (in Japanese) |
| [3] | Bahr, F.: Liniensieben und Quadratwurzelberechnung für das Zahlkörpersieb, University of Bonn (2005) |
| [4] | Cavallar, S.; Bosma, W., Strategies for filtering in the number field sieve, ANTS IV, 209-231 (2000), Heidelberg: Springer, Heidelberg · Zbl 1006.11076 |
| [5] | Cavallar, S.; Dodson, B.; Lenstra, A. K.; Leyland, P.; Montgomery, P. L.; Murphy, B.; te Riele, H.; Zimmermann, P.; Preneel, B., Factoring a 512-bit RSA modulus, Advances in Cryptology - EUROCRYPT 2000, 1-18 (2000), Heidelberg: Springer, Heidelberg · Zbl 1082.94511 · doi:10.1007/3-540-45539-6_1 |
| [6] | Coppersmith, D., Solving linear equations over GF(2): block Lanczos algorithm, Linear algebra and its applications, 192, 33-60 (1993) · Zbl 0788.65038 · doi:10.1016/0024-3795(93)90235-G |
| [7] | Coppersmith, D., Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm, Math. of Comp., 62, 333-350 (1994) · Zbl 0805.65046 · doi:10.2307/2153413 |
| [8] | Franke, J., Kleinjung, T.: Continued fractions and lattice sieving. In: Proceedings SHARCS 2005, http://www.ruhr-uni-bochum.de/itsc/tanja/SHARCS/talks/FrankeKleinjung.pdf |
| [9] | Kleinjung, T.: Cofactorisation strategies for the number field sieve and an estimate for the sieving step for factoring 1024-bit integers. In: Proceedings SHARCS 2006, http://www.hyperelliptic.org/tanja/SHARCS/talks06/thorsten.pdf. |
| [10] | Lenstra, A. K.; Lenstra, H. W., The development of the number field sieve (1993), Heidelberg: Springer, Heidelberg · Zbl 0777.00017 |
| [11] | Lenstra, A. K.; Verheul, E. R., Selecting cryptographic key sizes, J, of Cryptology, 14, 255-293 (2001) · Zbl 1006.94020 |
| [12] | Lenstra, H. W., Factoring integers with elliptic curves, Ann, of Math., 126, 649-673 (1987) · Zbl 0629.10006 |
| [13] | Montgomery, P. L.; Guillou, L. C.; Quisquater, J.-J., A block Lanczos algorithm for finding dependencies over GF(2), Advances in Cryptology - EUROCRYPT ’95, 106-120 (1995), Heidelberg: Springer, Heidelberg · Zbl 0973.11520 |
| [14] | Montgomery, P.L.: Square roots of products of algebraic numbers, http://ftp.cwi.nl/pub/pmontgom/sqrt.ps.gz · Zbl 0819.11069 |
| [15] | Nguyen, P.; Buhler, J. P., A Montgomery-like square root for the number field sieve, ANTS III, 151-168 (1998), Heidelberg: Springer, Heidelberg · Zbl 0983.11075 |
| [16] | Pomerance, C.: A tale of two sieves, http://www.ams.org/notices/199612/pomerance.pdf · Zbl 1042.11528 |
| [17] | Prime95, http://www.mersenne.org/freesoft.htm |
| [18] | Thomé, E., Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm, Journal of symbolic computation, 33, 757-775 (2002) · Zbl 1010.65024 · doi:10.1006/jsco.2002.0533 |
| [19] | Zimmermann, P.: http://gforge.inria.fr/projects/ecm/ |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
