A quadrant of residues

Question

Assume that following inequality holds $$\mathsf{w,x,y,z<AB,AC,AD,BC,BD,CD<ABC,ABD,ACD,BCD<wx,wy,wz,xy,xz,yz}$$ with $$\mathsf{gcd(A,B)=gcd(A,C)=gcd(A,D)=gcd(B,C)=gcd(B,D)=gcd(C,D)=1}$$

where we know $\mathsf{A,B,C,D}$ and we have following residue values: $$\mathsf{xz\bmod A,\quad wz\bmod C}$$ $$\mathsf{xy\bmod B,\quad wy\bmod D}$$

Is there a standard procedure to find $\mathsf{w,x,y,z}$?

Only standard procedure I can think of is exhaustive search which needs $\mathsf{(ABCD)^2}$ arithmetic operations. Is there a way to do this is say at most $\mathsf{(ABCD)^{\frac{1}\beta-\epsilon}}$ arithmetic operations where $\epsilon\in(0,\frac{1}\beta)$ with $\beta>2$ holds?

Answer 1

Partial answer giving probabilistic algorithm under assumptions which can be greatly relaxed.

wlog assume $AB$ is the smallest product.

Write $$ r_1= xz \mod A \qquad (1)$$ $$ r_2= xy \mod B \qquad (2)$$ $$ r_3= wz \mod C \qquad (3)$$ $$ r_4= wy \mod D \qquad (4)$$

Assume $r_1r_2$ is coprime to $AB$ and $r_3$ is coprime to $C$ and $r_4$ is coprime $D$.

Iterate $x_1$ from $1$ to $AB$.

Try to compute $z_1=r_1 x_1^{-1} \mod AB$ from (1) and $y_1=r_2 x_1^{-1} \mod AB$ from (2).

$(x_1,y_1,z_1)$ satisfy (1) and (2) and the required inequality.

Try to compute $w_1'=r_3 z_1^{-1}\mod C$ and $w_2'=r_4 y_1^{-1} \mod D$

Apply the Chinese remainder theorem to $w_1' \mod C,w_2' \mod D$ to get $w_1 \mod CD$.

If $w_1 < AB$, $(x_1,y_1,z_1,w_1)$ is solution.

The complexity is $O(AB)$.

The main source of possible failure is the last step.