1. (programming required) Modify your implementation of RSA to use the above idea 2. Actually, instead of computing a := c d mod p and b := c d mod q, we could have computed a := c d mod p−1 mod p and...

1. (programming required) Modify your implementation of RSA to use the above idea

2. Actually, instead of computing a := c d mod p and b := c
^d
mod q, we could have computed a := c
^d
mod p^{−1 mod}
p and b := c d mod q−1 mod q. Explain why this modification is valid. (This change can improve the efficiency of RSA, because now both the base and the exponent may be substantially smaller than they were in the regular RSA implementation.)