2. A common way to speed up RSA decryption incorporates the Chinese Remainder Theorem, as follows. Suppose that dl)y mod n and n pq. Define d-d mod (p-1) and d-d mod (q-1); and let M,-g" mod p and M,7-1 mod q. Then, consider the following algorithm: Algorithm 1. CRT-Optimized RSA Decryption (n, dp, dy, Mp, Mq, y) *p -y- mod,p return (x) The Algorithm 1 replaces an exponentiation modulo n by modular exponentiations modulo p and q. If p and q are l-bit integers and exponentiation modulo an l-bit integer takes time cl3, then the time to perform the required exponentiation is reduced from c(2)3 to 2c1, a saving of 75%. The final step, involving the Chinese Remainder Theorem, require O(P) if dp, dq, Mp, and Mg have been pre-computed. a. Prove that the value x returned by Algorithm 1 is, in fact, y mod n. b. Given that pl5, q-2003, and d-1234577, compute ,, dh Me, and M. c. Given the above values ofp, q, and d, decrypt the ciphertext152702 using Algorithm 2. A common way to speed up RSA decryption incorporates the Chinese Remainder Theorem, as follows. Suppose that dl)y mod n and n pq. Define d-d mod (p-1) and d-d mod (q-1); and let M,-g" mod p and M,7-1 mod q. Then, consider the following algorithm: Algorithm 1. CRT-Optimized RSA Decryption (n, dp, dy, Mp, Mq, y) *p -y- mod,p return (x) The Algorithm 1 replaces an exponentiation modulo n by modular exponentiations modulo p and q. If p and q are l-bit integers and exponentiation modulo an l-bit integer takes time cl3, then the time to perform the required exponentiation is reduced from c(2)3 to 2c1, a saving of 75%. The final step, involving the Chinese Remainder Theorem, require O(P) if dp, dq, Mp, and Mg have been pre-computed. a. Prove that the value x returned by Algorithm 1 is, in fact, y mod n. b. Given that pl5, q-2003, and d-1234577, compute ,, dh Me, and M. c. Given the above values ofp, q, and d, decrypt the ciphertext152702 using Algorithm