Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/ii/paper-2/12k/a/solution

In the Rabin cryptosystem, the public key is and encryption sends an encoded message to
Knowing , the receiver finds the two square roots modulo each prime and combines them with the Chinese remainder theorem to obtain four roots modulo ; prescribed redundancy identifies the intended one.
Omicron has
The Chinese remainder theorem determines uniquely modulo (assuming the independently generated moduli are coprime; a nontrivial gcd would itself factor them). Since , one has , so this residue is the ordinary integer . Taking its positive integer square root recovers .
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.

New to topics? Read the docs here!