doi.org

Factorization of a 768-Bit RSA Modulus

References

  1. Adleman, L.M.: Factoring numbers using singular integers. In: STOC, pp. 64–71. ACM, New York (1991)

    Google Scholar 

  2. Aoki, K., Franke, J., Kleinjung, T., Lenstra, A.K., Osvik, D.A.: A kilobit special number field sieve factorization. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 1–12. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  3. Bahr, F.: Liniensieben und Quadratwurzelberechnung für das Zahlkörpersieb, Diplomarbeit, University of Bonn (2005)

    Google Scholar 

  4. Bahr, F., Böhm, M., Franke, J., Kleinjung, T.: Factorization of RSA-200 (May 2005), http://www.loria.fr/~zimmerma/records/rsa200

  5. Buhler, J., Montgomery, P., Robson, R., Ruby, R.: Implementing the number field sieve. Technical report, Oregon State University (1994)

    Google Scholar 

  6. Cavallar, S.: Strategies in filtering in the number field sieve. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 209–232. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  7. Cavallar, S., Dodson, B., Lenstra, A.K., Lioen, W.M., Montgomery, P.L., Murphy, B., te Riele, H.J.J., Aardal, K., Gilchrist, J., Guillerm, G., Leyland, P.C., Marchand, J., Morain, F., Muffett, A., Putnam, C., Putnam, C., Zimmermann, P.: Factorization of a 512-bit RSA modulus. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 1–18. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  8. Coppersmith, D.: Solving linear equations over GF(2): block Lanczos algorithm. Linear Algebra and its Applications 192, 33–60 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  9. Coppersmith, D.: Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm. Math. Comput. 62(205), 333–350 (1994)

    MATH  MathSciNet  Google Scholar 

  10. Cowie, J., Dodson, B., Elkenbracht-Huizing, R.M., Lenstra, A.K., Montgomery, P.L., Zayer, J.: A world wide number field sieve factoring record: On to 512 bits. In: Kim, K.-c., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 382–394. Springer, Heidelberg (1996)

    Chapter  Google Scholar 

  11. Dixon, J.D.: Asymptotically fast factorization of integers. Math. Comp. 36, 255–260 (1981)

    MATH  MathSciNet  Google Scholar 

  12. Franke, J., Kleinjung, T.: Continued fractions and lattice sieving. In: Workshop record of SHARCS (2005), http://www.ruhr-uni-bochum.de/itsc/tanja/SHARCS/talks/FrankeKleinjung.pdf

  13. Golliver, R.A., Lenstra, A.K., McCurley, K.S.: Lattice sieving and trial division. In: Huang, M.-D.A., Adleman, L.M. (eds.) ANTS 1994. LNCS, vol. 877, pp. 18–27. Springer, Heidelberg (1994)

    Google Scholar 

  14. Kleinjung, T.: Cofactorisation strategies for the number field sieve and an estimate for the sieving step for factoring 1024 bit integers. In: Workshop record of SHARCS (2005), http://www.hyperelliptic.org/tanja/SHARCS/talks06/thorsten.pdf

  15. Kleinjung, T.: On polynomial selection for the general number field sieve. Math. Comp. 75, 2037–2047 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  16. Kleinjung, T.: Polynomial selection. Presented at the CADO Workshop on Integer Factorization (2008), http://cado.gforge.inria.fr/workshop/slides/kleinjung.pdf

  17. Lenstra, A.K.: Computational methods in public key cryptology. In: Coding theory and cryptology. Lecture Notes Series, pp. 175–238. Institute for Mathematical Sciences, National University of Singapore (2002)

    Google Scholar 

  18. Lenstra, A.K., Lenstra Jr., H.W.: Algorithms in number theory. In: Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, pp. 673–716. Elsevier, Amsterdam (1990)

    Google Scholar 

  19. Lenstra, A.K., Lenstra Jr., H.W.: The Development of the Number Field Sieve. LNM, vol. 1554. Springer, Heidelberg (1993)

    MATH  Google Scholar 

  20. Lenstra, A.K., Lenstra Jr., H.W., Manasse, M.S., Pollard, J.M.: The factorization of the ninth Fermat number. Math. of Comp. 61(203), 319–349 (1993)

    MATH  MathSciNet  Google Scholar 

  21. Lenstra, A.K., Tromer, E., Shamir, A., Kortsmit, W., Dodson, B., Hughes, J., Leyland, P.C.: Factoring estimates for a 1024-bit RSA modulus. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 55–74. Springer, Heidelberg (2003)

    Google Scholar 

  22. Massey, J.: Shift-register synthesis and BCH decoding. IEEE Trans Information Theory 15, 122–127 (1969)

    Article  MATH  MathSciNet  Google Scholar 

  23. Montgomery, P.: Square roots of products of algebraic numbers, http://ftp.cwi.nl/pub/pmontgom/sqrt.ps.gz

  24. Montgomery, P., Murphy, B.: Improved polynomial selection for the number field sieve. Technical report, the Fields institute, Toronto, Ontario, Canada (June 1999)

    Google Scholar 

  25. Morrison, M.A., Brillhart, J.: A method of factoring and the factorization of F 7. Math. of Comp. 29(129), 183–205 (1975)

    MATH  MathSciNet  Google Scholar 

  26. Murphy, B.: Modelling the yield of number field sieve polynominals. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 137–150. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  27. National Institute of Standards and Technology. Discussion paper: the transitioning of cryptographic algorithms and key sizes, http://csrc.nist.gov/groups/ST/key_mgmt/documents/Transitioning_CryptoAlgos_070209.pdf

  28. National Institute of Standards and Technology. Special publication 800-57: Recommendation for key management part 1: General (revised), http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf

  29. Nguyen, P.Q.: A Montgomery-like square root for the number field sieve. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 151–168. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  30. Pollard, J.M.: The lattice sieve. In: [19], pp. 43–49

    Google Scholar 

  31. Pomerance, C.: Analysis and comparison of some integer factoring algorithms. In: Lenstra Jr., H.W., Tijdeman, R. (eds.) Computational Methods in Number Theory, Math. Centrum Tract, Amsterdam, vol. 154, pp. 89–139 (1982)

    Google Scholar 

  32. Pomerance, C.: The quadratic sieve factoring algorithm. In: Beth, T., Cot, N., Ingemarsson, I. (eds.) EUROCRYPT 1984. LNCS, vol. 209, pp. 169–182. Springer, Heidelberg (1985)

    Chapter  Google Scholar 

  33. Pomerance, C.: A tale of two sieves (1996), http://www.ams.org/notices/199612/pomerance.pdf

  34. Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM 21, 120–126 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  35. RSA the security division of EMC. The RSA challenge numbers. formerly on http://www.rsa.com/rsalabs/node.asp?id=2093 , now on http://en.wikipedia.org/wiki/RSA_numbers

  36. RSA the security division of EMC. The RSA factoring challenge FAQ, http://www.rsa.com/rsalabs/node.asp?id=2094

  37. Tarantino, Q.: That’s a bingo! http://www.youtube.com/watch?v=WtHTc8wIo4Q , http://www.imdb.com/title/tt0361748/quotes

  38. Thomé, E.: Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm. Journal of Symbolic Computation 33(5), 757–775 (2002)

    Article  MATH  MathSciNet  Google Scholar 

Download references