Abstract
We use the specific structure of the inputs to the cofactorization step in the general number field sieve (GNFS) in order to optimize the runtime for the cofactorization step on a hardware cluster. An optimal distribution of bitlength-specific ECM modules is proposed and compared to existing ones. With our optimizations we obtain a speedup between 17% and 33% of the cofactorization step of the GNFS when compared to the runtime of an unoptimized cluster.
Chapter PDF
Similar content being viewed by others
Keywords
References
Bellman, R.: Dynamic Programming. Princeton University Text (1957)
Cohen, H.: A course in computational algebraic number theory. Springer, Berlin (1997)
Franke, J., Kleinjung, T.: RSA 640 (2005), http://www.crypto-world.com/announcements/rsa640.txt
Franke, J., Kleinjung, T.: Continued Fractions and Lattice Sieving (Unpublished) (2006), http://www.math.uni-bonn.de/people/thor/confrac.ps
von zur Gathen, J., Güneysu, T., Kargl, A., Loebenberger, D., Paar, C., Putzka, J.: Faktorisierung großer Zahlen: Hardware für Elliptische Kurven Faktorisierung. Technical report, HGI Bochum, b-it Bonn & Siemens AG München (2007)
Kleinjung, T.: Cofactorisation Strategies for the Number Field Sieve and an Estimate for the Sieving Step for Factoring 1024-bit Integers (Unpublished) (2004), http://www.math.uni-bonn.de/people/thor/cof.ps
Kleinjung, T.: On Polynomial Selection for the General Number Field Sieve. Mathematics of Computation 75(256), 2037–2047 (2006), http://dx.doi.org/10.1090/S0025-5718-06-01870-9
Kumar, S., Paar, C., Pelzl, J., Pfeiffer, G., Schimmler, M.: Breaking ciphers with COPACOBANA –A Cost-Optimized Parallel Code Breaker. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 101–118. Springer, Heidelberg (2006), http://dx.doi.org/10.1007/11894063_9
Lenstra, A.K., Lenstra Jr., H.W. (eds.): The development of the number field sieve. Lecture Notes in Mathematics, vol. 1554. Springer, Berlin (1993)
Lenstra Jr., H.W.: Factoring integers with elliptic curves. Annals of Mathematics 126, 649–673 (1987)
Pollard, J.M.: Theorems on factorization and primality testing. Proceedings of the Cambridge Philosophical Society 76, 521–528 (1974)
RSA Laboratories. The RSA Challenge Numbers (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Loebenberger, D., Putzka, J. (2009). Optimization Strategies for Hardware-Based Cofactorization. In: Jacobson, M.J., Rijmen, V., Safavi-Naini, R. (eds) Selected Areas in Cryptography. SAC 2009. Lecture Notes in Computer Science, vol 5867. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-05445-7_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-05445-7_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-05443-3
Online ISBN: 978-3-642-05445-7
eBook Packages: Computer ScienceComputer Science (R0)