Is it possible to use The Jubjub bird and The frumious Bandersnatch method in this polynomial?

[Alberico Lepore]

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

************************************************************************************************
OTHER INFORMATION
************************************************************************************

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

really is O(8)


(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

[Alberico Lepore]

N=p*q

with

p+q=8*x+4

[Alberico Lepore]

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 ?

[Alberico Lepore]

(65-8 * b) * (67-8 * a) -1763 = 0
->
(8*a*b-65*a-67*b+324)=0 which is irreducible

pag 3
http://www.crypto-uni.lu/jscoron/pub.../bivariate.pdf

[Alberico Lepore]

can we use the Coppersmith method multivariate in this case?


(8*a*b-65*a-67*b+5) mod 319 = 0

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

[Alberico Lepore]

Originally Posted by Alberico Lepore

(65-8 * b) * (67-8 * a) -1763 = 0
->
(8*a*b-65*a-67*b+324)=0 which is irreducible

pag 3
http://www.crypto-uni.lu/jscoron/pub.../bivariate.pdf

p(x, y) = a + bx + cy + dxy ;

X*Y < W^(2/3δ) ;

W = max{|a|, |b|X, |c|Y, |d|XY }

we can easily choose | d | XY of the order size N ^ 2 and X * Y of the order size of N.

that is the problem?