Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/ii/paper-2/12k/a/solution
Past exam of the mathematics course of the University of Cambridge 2022 ii Paper 2 12K a Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
In the Rabin cryptosystem, the public key is and encryption sends an encoded message toKnowing , 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 hasThe 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!