Past exam of the mathematics course of the University of Cambridge / 2025 / ia / Paper 4 / 6E / f

RSA chooses $n=pq$ and exponents $e,d$ with $ed\equiv 1(\mathrm{mod}\varphi (n))$. The public key is $(n,e)$, encryption is $c\equiv m^e(\mathrm{mod}n)$, and the secret exponent decrypts via $c^d\equiv m(\mathrm{mod}n)$. Security relies on the difficulty of recovering $\varphi (n)$ from a large unfactored $n$.