Analysis of Bernstein's factorization circuit
D.J. Bernstein has proposed a circuit-based implementation of the matrix step of the number field sieve factorization algorithm (see "Circuits for integer factorization: a proposal", http://cr.yp.to/papers.html#nfscircuit, 2001). These circuits offer an asymptotic cost reduction under the measure "construction cost × run time". We evaluate the cost of these circuits, in agreement with Bernstein, but argue that, compared to previously known methods, these circuits can factor integers that are 1.17 times larger, rather than 3.01 as claimed (and even this is only under the non-standard cost measure). We also propose an improved circuit design based on a new mesh routing algorithm, and show that, for factorization of 1024-bit integers, the matrix step can, under an optimistic assumption about the matrix size, be completed within a day by a device that costs a few thousand dollars. We conclude that from a practical standpoint, the security of RSA relies exclusively on the hardness of the relation collection step of the number field sieve
Cite this item
Lenstra, A. K., Shamir, A., Tomlinson, J., & Tromer, E. (2002). Analysis of Bernstein’s factorization circuit. Advances in Cryptology - ASIACRYPT 2002. 8th International Conference on the Theory and Application of Cryptology and Information Security. Proceedings, Lecture Notes in Computer Science; 2501, 1–26. https://doi.org/10.1007/3-540-36178-2_1
Click Copy to copy the citation, or select the text manually.
EPFL-CONF-149708.pdf
openaccess
287.02 KB
Adobe PDF
599c508d272b85fc6c2f769c0203b14e