Chapter 4, Problem 47C

Communication security is extremely important in computer networks, and one way many network protocols achieve security is to encrypt messages. Typical cryptographic schemes for the secure transmission of messages over such networks are based on the fact that no efficient algorithms are known for factoring large integers. Hence, if we can represent a secret message by a large prime number p, we can transmit, over the network, the number r = p · q, where q > p is another large prime number that acts as the encryption key. An eavesdropper who obtains the transmitted number r on the network would have to factor r in order to figure out the secret message p.

Using factoring to figure out a message is hard without knowing the encryption key q. To understand why, consider the following naive factoring algorithm:

for (int p=2; p < r; p++)

if (r % p == 0)

return "The secret message is p!";

1. a. Suppose the eavesdropper’s computer can divide two 100-bit integers in μs (1 millionth of a second). Estimate the worst-case time to decipher the secret message p if the transmitted message r has 100 bits.
2. b. What is the worst-case time complexity of the above algorithm? Since the input to the algorithm is just one large number r, assume that the input size n is the number of bytes needed to store r, that is, $n=\lfloor ({\text{log}}_{\text{2}}r)/\text{8}\rfloor +1$, and that each division takes time O(n).