Finding Small Roots of Bivariate Integer Polynomial Equations: A Direct Approach
DOI: 10.1007/978-3-540-74143-5_21
关键词:
摘要: Coppersmith described at Eurocrypt 96 an algorithm for finding small roots of bivariate integer polynomial equations, based on lattice reduction. A simpler was later proposed in [9], but it asymptotically less efficient than Coppersmith's algorithm. In this paper, we describe analogous simplification with the same asymptotic complexity as Coppersmith. We illustrate our new problem factoring RSA moduli high-order bits known; practical experiments method is several orders magnitude faster [9].
springer.com
sci-hub.st 参考文章(36)
Aggelos Kiayias, Moti Yung, Self Protecting Pirates and Black-Box Traitor Tracing international cryptology conference. pp. 63- 79 ,(2001) , 10.1007/3-540-44647-8_4
Alexander May, Computing the RSA Secret Key Is Deterministic Polynomial Time Equivalent to Factoring Advances in Cryptology – CRYPTO 2004. pp. 213- 219 ,(2004) , 10.1007/978-3-540-28628-8_13
Phong Q. Nguên, Damien Stehlé, Floating-Point LLL revisited theory and application of cryptographic techniques. pp. 215- 233 ,(2005) , 10.1007/11426639_13
Alexander May, Cryptanalysis of Unbalanced RSA with Small CRT-Exponent Advances in Cryptology — CRYPTO 2002. pp. 242- 256 ,(2002) , 10.1007/3-540-45708-9_16
Nicholas Howgrave-Graham, Finding Small Roots of Univariate Modular Equations Revisited Lecture Notes in Computer Science. pp. 131- 142 ,(1997) , 10.1007/BFB0024458
Dan Boneh, Glenn Durfee, Cryptanalysis of RSA with private key d less than N 0:292 theory and application of cryptographic techniques. pp. 1- 11 ,(1999) , 10.1007/3-540-48910-X_1
Johannes Blömer, Alexander May, A tool kit for finding small roots of bivariate polynomials over the integers theory and application of cryptographic techniques. pp. 251- 267 ,(2005) , 10.1007/11426639_15
Dan Boneh, Glenn Durfee, Nick Howgrave-Graham, Factoring N = prq for Large r international cryptology conference. pp. 326- 337 ,(1999) , 10.1007/3-540-48405-1_21
Don Coppersmith, Finding a small root of a univariate modular equation theory and application of cryptographic techniques. pp. 155- 165 ,(1996) , 10.1007/3-540-68339-9_14
Jean-Sébastien Coron, Finding Small Roots of Bivariate Integer Polynomial Equations Revisited theory and application of cryptographic techniques. pp. 492- 505 ,(2004) , 10.1007/978-3-540-24676-3_29