Topic: Number Theory

Q. Recall that an EAO (elementary arithmetic operation) consists of adding, subtracting, multiplying, doing division with remainder to two integers, or taking the ceiling of the square root of an integer.

Company A decides to implement RSA for its employees by generating a common, company-wide RSA modulus n, then distributing a unique encryption/decryption exponent pair ( e_i, d_i ) to each employee i. Suppose the CEO of company B wants to send a message M Z / nZ to two employees of company A, say employes i = 1, 2. Thus the CEO computes and sends the ciphertexts

C₁ M^e₁ mod n C₂ M^e₂mod n

Assume that gcd( e₁, e₂ ) = 1. Explain how Eve, an eavesdropper who sees C1, C2, can efficiently compute M

( and explain why its efficient, i.e. runs in O( log n ) EAOs ).