Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 4 / 3H / Solution

A Rabin cryptosystem chooses Blum primes $p,q$, publishes $N=pq$, and encrypts $m$ as $c=m^2\mathrm{mod}N$. Decryption takes square roots modulo $p$ and $q$, combines them with CRT, and uses redundancy to select the intended one of four roots. Here $2355^2\equiv 25(\mathrm{mod}2773)$, while the obvious root is $5$. ThusSo $2773=47\cdot 59$ is factored, allowing all future square roots and hence all ciphertexts to be decrypted.