Paper 2, Section II, D
(a) Define the Euler function . State the Chinese remainder theorem, and use it to derive a formula for when is a product of distinct primes. Show that there are at least ten odd numbers with a power of 2 .
(b) State and prove the Fermat-Euler theorem.
(c) In the RSA cryptosystem a message is encrypted as . Explain how and should be chosen, and how (given a factorisation of ) to compute the decryption exponent . Prove that your choice of works, subject to reasonable assumptions on . If and then what is ?
Typos? Please submit corrections to this page on GitHub.