How does sagemath solve X*a*b+Y*a+Y*b+Z mod N = 0 knowing X,Y,Z,N without factoring N? Is there a computationally efficient way to solve this?

edit

The method I propose is coccinella's bruteforce.

If N=(6a+1)(6*b+1) and a and b are odd and such that a mod 8 = b mod 8

We must find

X and Y such that

Ya=8G+3 : Yb=8F+3

X is of the same order of magnitude as N (or even a few missing digits are fine)

N mod X is as low as possible and Y is as low as possible or as close as possible to X (such that (X-Y)a and (X-Y)b are of the same order of magnitude as X).

Example: N=2449=31*79

2449-(31*79-1)/6=2041

ab+2041a+2041b+2381=2449W

a mod 8 = b mod 8 = 5

So we need to find Y mod 8 = 7

Let's try X = 1245

12452041 mod 2449 = 1432 (1432-1245=187 -> 187a and 187*b are of the same order as X, so it's fine)

1432 mod 8 = 0 (remember, we need to subtract 1)

So the new equation will be

1245ab+1432a+1432b+1055=2449*V

2449V-1055-a-b-(2(1431-1245)/2)^2-(2(1431-1245)/2)(a-1431)-(2(1431-1245)/2)^2-(2 (1431-1245)/2)(b-1431)=1245W

187a+187b+41V+1055=1245j , 1245ab+1432a+1432b+1055=2449V , (6a+1)(6b+1)=2449 , j=5

-> a=5 ; b=13

Now I'll explain this to you

2449V-1055-a-b-(2(1431-1245)/2)^2-(2(1431-1245)/2)(a-1431)-(2(1431-1245)/2)^2-(2(1431-1245)/2)(b-1431)=1245W

pq=8G+3 and such that

pq-(2(q-X)/2)^2-(2(q-X)/2)(p-q)=X*(p+q-X)

In our case, p=a & p=b & q=1431