Bivariate Coppersmith method

edit

Given the bivariate polynomial

p(m,n) = 675 * m * n + 297 * m + 25 * n + 11

The bivariate Coppersmith method can be used to find m0 and n0 such that

(675 * m0 * n0 + 297 * m0 + 25 * n0 + 11) mod (1763) = 0

where is it

m0 = 3 ; n0 = 3

Unfortunately I cannot understand the hypotheses

Kindly someone could only explain the hypotheses to me

EDIT1:

OTHER INFORMATION

You can choose some coefficients and their size order of this type of polynomial in O (16).

(N-3)/8-q*(p-A)/8-[4-(A-7)*(A-5)/8]=A*(q+A-4-8)/8

->

N=p*q

if we choose A such that p-A mod 8 = 0 



we can write it this way


(N-3)/8-Q-[4-(A-7)*(A-5)/8]=A*X

so there are 4 chances to find A and they are

8*h+1 ; 8*h+3 ; 8*h+5 ; 8*h+7



(N-3)/8-p*(q-B)/8-[4-(B-7)*(A-5)/8]=B*(p+B-4-8)/8

->

N=p*q

if we choose B such that q-B mod 8 = 0



we can write it this way


(N-3)/8-P-[4-(B-7)*(B-5)/8]=B*Y

so there are 4 chances to find B and they are

8*k+1 ; 8*k+3 ; 8*k+5 ; 8*k+7


f(N,A,B) is  O(16)





Example

1763=41*43


220-q*(p-25)/8-[4-(25-7)*(25-5)/8]=25*(q+25-4-8)/8

220-p*(q-27)/8-[4-(27-7)*(27-5)/8]=27*(p+B-4-8)/8


220-Q-[4-(25-7)*(25-5)/8]=25*X

220-P-[4-(27-7)*(27-5)/8]=27*X


Q=25*a+11   X=10-a  

P=27*b+1    X=10-b 


220-Q-[4-(17-7)*(17-5)/8]=17*X

Q=17*c+10   X=13-c      9-a=13-c -> c=a+4

220-P-[4-(19-7)*(19-5)/8]=19*X

P=19*d+9    X=12-d      9-b=12-d  ->d=b+3



p=(19*(b+3)+9)-(27*b+1)=65-8*b      

q=(17*(a+4)+10)-(25*a+11)=67-8*a    



(65-8*b)*(67-8*a)=1763
,
(10-a)-(10-b)=((67-8*a)-(65-8*b)-2)/8


(65-8*b)*(27*1763)/(-8*(27*b+1)+1763)=1763 TRUE




So I thought about using the bivariate Coppersmith method

Q=25*a+11 

P=27*b+1


p(m,n)=p(b,a)=P*Q=(27*b+1)*(25*a+11)=Z*1763

EDIT2:

At least see if I understand:

in my case given two polynomials

for example

(25*a+11)*(27*b+1) mod 1763 ==0

and

(17*(a+4)+10)*(19*(b+3)+9) mod 1763 == 0

the first question is can they be both modulo 1763?

|a|<IntegerPart[sqrt(1763/2)]

|b|<2*IntegerPart[sqrt(1763/2)]

if this method can be applied, it can be solved in polynomial time

Did I get it right ?