Paper 2, Section II, D

Numbers and Sets | Part IA, 2020

(a) Define the Euler function ϕ(n)\phi(n). State the Chinese remainder theorem, and use it to derive a formula for ϕ(n)\phi(n) when n=p1p2prn=p_{1} p_{2} \ldots p_{r} is a product of distinct primes. Show that there are at least ten odd numbers nn with ϕ(n)\phi(n) a power of 2 .

(b) State and prove the Fermat-Euler theorem.

(c) In the RSA cryptosystem a message m{1,2,,N1}m \in\{1,2, \ldots, N-1\} is encrypted as c=mec=m^{e} (modN)(\bmod N). Explain how NN and ee should be chosen, and how (given a factorisation of NN ) to compute the decryption exponent dd. Prove that your choice of dd works, subject to reasonable assumptions on mm. If N=187N=187 and e=13e=13 then what is dd ?

Typos? Please submit corrections to this page on GitHub.