A Tool Kit for Finding Small Roots of Bivariate Polynomials over the Integers

详细信息    查看全文

• 作者：Johannes Bl?mer ; Alexander May
• 关键词：Coppersmith’s method ; univariate vs. bivariate ; RSA
• 刊名：Lecture Notes in Computer Science
• 出版年：2005
• 出版时间：2005
• 年：2005
• 卷：3494
• 期：1
• 页码：p.251
• 全文大小：334 KB
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

We present a new and flexible formulation of Coppersmith’s method for finding small solutions of bivariate polynomials p(x,y) over the integers. Our approach allows to maximize the bound on the solutions of p(x,y) in a purely combinatorial way. We give various construction rules for different shapes of p(x,y)’s Newton polygon. Our method has several applications. Most interestingly, we reduce the case of solving univariate polynomials f(x) modulo some composite number N of unknown factorization to the case of solving bivariate polynomials over the integers. Hence, our approach unifies both methods given by Coppersmith at Eurocrypt 1996.