= Solution
In the <Rabin cryptosystem>, the public key is $N=pq$ and encryption sends an encoded message $m$ to
$$
c\equiv m^2\pmod N.
$$
Knowing $p,q$, the receiver finds the two square roots modulo each prime and combines them with the <Chinese remainder theorem> to obtain four roots modulo $N$; prescribed redundancy identifies the intended one.
Omicron has
$$
m^2\equiv c\pmod N,\qquad m^2\equiv c'\pmod{N'}.
$$
The Chinese remainder theorem determines $m^2$ uniquely modulo $NN'$ (assuming the independently generated moduli are coprime; a nontrivial gcd would itself factor them). Since $1\leq m<N<N'$, one has $m^2<NN'$, so this residue is the ordinary integer $m^2$. Taking its positive integer square root recovers $m$.
This does not normally decrypt another ciphertext sent under only one modulus. The recovered pair reveals no nontrivial square root collision modulo that modulus and hence supplies no factorization; breaking a single Rabin instance remains equivalent to factoring its modulus.
Back to article page
