Question. You encrypt a message using the RSA encryption system as t^e mod n, where t, e < n and t is the numerical equivalent of the message. The message is written in a 27-letter alphabet and is split into blocks with m characters each. You have a limit of 10¹² binary operations to encrypt each block. Estimate the largest possible value of m if you use the fast exponentiation algorithm and

(a) standard algorithms for division and multiplication, which we assume require 100.log₂a.log₂b binary operation to find ab and to find the quotient and remainder when a is divided by b;

(b) the best known algorithms for division and multiplication, which we assume for a ≥ b require

100.(log₂ a).(log₂ log₂ a) . (log₂ log₂ log₂ a)

binary operation to find ab and to find the quotient and remainder when a is divided by b.

Remark. You may assume that the number of operations in the fast exponentiation algorithm is twice more than the number of operations needed for all squarings.

The number of operations needed to convert the message into a number is small and can be ignored. You may also ignore the difference between n and Φ(n).

In part (b) you have to solve a transcendental equation. During the calculations you can round the results of iterations to the nearest integer.