Bivariate Coppersmith method
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 ?
Your question would be better addressed to https://math.stackexchange.com/ : this forum is oriented towards the use of Sagemath to execute mathematical computations ; mathematical foundations are discussed only when this is relevant to computation.
@Emmanuel Charpentier is there any method to use bivariate coppersmith method in sagemath?
Some implementation is available at https://github.com/ubuntor/coppersmit...
@Max Alekseyev thank you
@Max Alekseyev I shared other information .[] @Emmanuel Charpentier if the bivariate Coppersmith method is applicable is relevant to computation of factorization