A tool kit for finding small roots of bivariate polynomials over the integers
作者： Johannes Blömer , Alexander May
DOI: 10.1007/11426639_15
关键词:
摘要: We present a new and flexible formulation of Coppersmith's method for finding small solutions bivariate polynomials p(x,y) over the integers. Our approach allows to maximize bound on in purely combinatorial way. give various construction rules different shapes p(x,y)'s Newton polygon. has several applications. Most interestingly, we reduce case solving univariate f(x) modulo some composite number N unknown factorization Hence, our unifies both methods given by Coppersmith at Eurocrypt 1996.
springer.com
core.ac.uk
sci-hub.st 参考文章(18)
Johannes Blömer, Alexander May, New Partial Key Exposure Attacks on RSA Advances in Cryptology - CRYPTO 2003. pp. 27- 43 ,(2003) , 10.1007/978-3-540-45146-4_2
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
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, 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
Alexander May, Secret Exponent Attacks on RSA-type Schemes with Moduli N = p r q public key cryptography. pp. 218- 230 ,(2004) , 10.1007/978-3-540-24632-9_16
D. Boneh, G. Durfee, Cryptanalysis of RSA with private key d less than N/sup 0.292/ IEEE Transactions on Information Theory. ,vol. 46, pp. 1339- 1349 ,(2000) , 10.1109/18.850673
László Csirmaz, The Size of a Share Must Be Large Journal of Cryptology. ,vol. 10, pp. 223- 231 ,(1997) , 10.1007/S001459900029
Don Coppersmith, Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities Journal of Cryptology. ,vol. 10, pp. 233- 260 ,(1997) , 10.1007/S001459900030