Bivariate Coppersmith Algorithm

asked 2026-09-23 15:12:24 +0200

Periodic_1_6 gravatar image

updated 2026-09-23 15:13:55 +0200

Given the two congruences:

(xy - Ax + B) mod C = 0

(xy - ax + b) mod c = 0

and knowing that:

|y| < x <= X

and

gcd(C, c) = 1

Could any of you kindly provide an implementation of a generic bivariate Coppersmith algorithm that automatically guarantees success for this type of polynomial and any given bound?

Example

(xy-46652x+46570) mod 373291 = 0

(xy-46653x+46571) mod 373299 = 0

|y| < x <= 27

gcd(373291,373299)=1

edit retag flag offensive close merge delete