To speed up RSA encryption, one may choose a very small encryption exponent. This exercise develops a "small encryption exponent attack" on RSA. Suppose Bob, Bill, and Betty have RSA public keys with moduli and , and all three use encryption exponent 3. Assume that is pairwise relatively prime. Suppose that Alice sends an encryption of the same message to Bob, Bill, and Betty; that is, Alice encodes her message as an integer with , and computes the three encrypted messages , for . Show how to recover Alice's message from these three encrypted messages.

722