1.(40 points)RSA algorithms are widely used to generate public and private key pairs. A pair of public and private key can be generated using the following steps:

* Find large primes p and a (p, q are only known to the key owner). * Compute n = p*q. Let (n) denote the number of prime numbers that are less than n. According to number theory, if n can be factored into the product of two prime numbers, then o(n) = (p-1)*(9-1). * Choose an e that is relatively prime to o (n) (i.e., the greatest common divisor between e and O(n) is 1), and the public key = . * Find multiplicative inverse d of e mod o (n) (i.e., find d such that e*d mod O(n) = 1), and the private key = . Let e and d denote the public and private key respectively. Answer the following questions: (a) (5 points) A public key is used to encrypt a plaintext M (M<>