Bivariate Coppersmith algorithm

The bivariate Coppersmith algorithm (opens new window) is a technique to solve polynomial equations of the form p(x,y)=0p(x, y) = 0 p ( x , y ) = 0 over the integers Z\mathbb{Z} Z , given that the solutions are within specific bounds: ∣x∣<X|x| < X ∣ x ∣ < X and ∣y∣<Y|y| < Y ∣ y ∣ < Y .

Suppose p(x,y)=∑ijpijxiyjp(x, y) = \sum_{ij} p_{ij}x^i y^j p ( x , y ) = ∑ ​ i j ​ ​ p ​ i j ​ ​ x ​ i ​ ​ y ​ j ​ ​ has degree δ\delta δ in each variable. Define D=maxij∣pij∣XiYjD = max_{ij} |p_{ij|}X^i Y^j D = m a x ​ i j ​ ​ ∣ p ​ i j ∣ ​ ​ X ​ i ​ ​ Y ​ j ​ ​ . The algorithm finds a solution (x,y)(x, y) ( x , y ) (if it exists) provided that:

The definitions of X,Y,DX, Y, D X , Y , D appear circular, but it’s not a problem, the condition implies there is pijp_{ij} p ​ i j ​ ​ such that:

Leave a Comment