if we can represent a secret message by a large prime number p, we can transmit,
ID: 3638522 • Letter: I
Question
if we can represent a secret message by a large prime number p, we can transmit, over a 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 very difficult without knowing the encryption key q. To understand why. consider the following naive factoring algorithmfor p =2, ...., r -1 do
if p divides r then
return "the secret message is p!"
A) suppose that the eaves dropper uses the above algorithm and has a computer that can carry out in 1 microsecond a division between two integers of up to 100 bits each. Give an estimate of the time that it will take in the worst case to decipher the secret message p if the transmitted message r has 100 bits.
B0 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 = [(log2r)/8] + 1], and that each division takes time O(n).
Explanation / Answer
a-
The worst case occurs when p and q are of equal size. If either p > q or p < q we can find one of them before the other and if we have one prime factor we can get the other one by performing one single division. We therefore assume that p and q are of equal size.
The size of p is m/2 where m is the size of r in bits. Our algorithm therefore runs in time 2m/2 (exponential time). This is clearly very inefficient. Generally, problems that requires exponential time are not considered to have a solution on a computer when the exponent becomes big.
On the particular case when we have a computer that performs one division in time 10-6 seconds we get the following running time for m=100:
2m/2 * 10-6 = 2100/2 * 10-6 = 1125899907 seconds = 35 years
b-
From the a-excercise we have learnt that in the worst case scenario we have to perform 2m/2 divisions where m is the number of bits in r. The number of bits in r arelog2r. Therefore we have 2(log2r)/2 = 24(log2r)/8 = 24n divisions. If each division takes time O(n) we then have time O(n24n).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.