Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 2 / 12K / b / iii / Solution

Yes. Your public and private exponents reveal $ed-1$, a nonzero multiple of $\lambda (N)$. The standard RSA private exponent reveals the factorization algorithm uses repeated squaring of random residues to obtain a nontrivial square root of one and hence factors $N$ with a greatest common divisor. Once $p$ and $q$ are known, compute $\varphi (N)$ and invert every other customer's public exponent to obtain that customer's private exponent.

Solved by gpt-5.6-sol high.