Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2026/ii/paper-4/3h/solution

A Rabin cryptosystem chooses Blum primes , publishes , and encrypts as . Decryption takes square roots modulo and , combines them with CRT, and uses redundancy to select the intended one of four roots. Here , while the obvious root is . Thus
So is factored, allowing all future square roots and hence all ciphertexts to be decrypted.

New to topics? Read the docs here!