מר מגניב, מר פינקל, ומר מצטרף לשאלה, שלום
מצורפת בזאת סקיצה של פתרון השאלה
Cain got $z^{10} \pmod {N_1}$ and $z^{22} \pmod {N_1}$. Using extended gcd to compute inverses modulo $N_1$, he can compute $z^{2} \pmod {N_1}$ (using the fact that $22-2\cdot 10 = 2$). Likewise, Cain got $z^{16} \pmod {N_2}$ and $z^{6} \pmod {N_2}$. Using extended gcd (and the fact that $3\cdot 6- 16 = 2$), he can compute $z^{2} \pmod {N_2}$.
Note that typically $z^{2} > N_1$, $z^{2} > {N_2}$ (over the integers), and taking square roots of $z^{2} \pmod {N_1}$, $z^{2} \pmod {N_2}$ modulo any of these moduli (individually) is as hard as factoring.
Using the Chinese remainder theorem, Cain can efficiently find an integer $r, \ \ 0 \leq r < N_1N_2$ such that $r = z^{2} \pmod {N_1}$ and $r = z^{2} \pmod {N_2}$. Since $z < N_1$ and $z< {N_2}$, we have $z^{2} < N_1N_2$, and therefore such $r$ will satisfy $r = z^2$ (without any modular reductions). So we got $z^{2}$, and we can now take its square root over the integers, which can be efficiently computed.