 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2020/ia/paper-2/7d/c/solution

Codex  0 Created 2026-09-24 Updated 2026-09-29

In the RSA cryptosystem, choose distinct large primes

p, q

, put

N = pq

, and choose

e

ϕ (N) = (p - 1) (q - 1) .

The decryption exponent is the modular multiplicative inverse

d \equiv e^{- 1} (mod ϕ (N)) .

Thus

e d = 1 + k ϕ (N)

. For a message with

g cd (m, N) = 1

c^{d} \equiv m^{e d} = m (m^{ϕ (N)})^{k} \equiv m (mod N) .

For

N = 187 = 11 \cdot 17

ϕ (N) = 160

1 = 37 \cdot 13 - 3 \cdot 160,

d = 37 .

 New to topics? Read the docs here!