Prime Number Theorem The key generation of several standard cryptosystems , e . RSA encryption , you have to gener ate a random prime number of fixed...

di

Prime Number TheoremThe key generation of several standard cryptosystems , e . g . RSA encryption , you have to generate a random prime number of fixed size , i . e . with a fixed number of digits . Ann - digit decimalumber is an integer in the range ( 109 - 1 102 - 1 , but note that this range is exactly 90% ofthe range In = (1 .. . 10" ) , so below we will pretend that choosing an n - digit random primes the same as choosing a random prime in RunBecause we have efficient algorithms to test whether any number a is prime , we can picka random prime in In by recursing on the following loop : Choose a random integer * in Pincheck if it is a prime , if so output it and stop , else repeatIn the exercise below use the following probabilistic fact : If you have an experiment whichsucceeds with probability p then the expected number of times you need to repeat this experiment to get at least one success is 1 / p . Consider this example : A dice shows " I " withprobability p = 1 / 6 , and if you are throwing a dice over and over until you get the first " I "you should expect to get one after 1 / p = 6 throws1 . Use the Prime Number Theorem to approximate how many times the above loop willexecute until a random n- digit prime is found for n = 102 . Use the Prime Number Theorem to approximate how many times the above loop willexecute until a random n- digit prime is found for n = 1003 . Use the Prime Number Theorem to approximate how many times the above loop willexecute until a random n- digit prime is found for n = 10904 . Conclude with a hypothesis about the efficiency of the key generation algorithm whichchooses an n- digit prime using the method above . The running time should be somefunction of n , the length of the prime . ( The running time of key generation as a functionof n is of paramount importance because in these encryption algorithms n will be thelength of the generated key , and the longer n is the stronger the cryptosystem will beagainst known attacks against it . )