a) For which type of modulus p is this method more powerful b) Describe roughly the running-time of the algorithm

*Please go step by step and explain why and how you got it*

3. Pohlig-Hellman algorithm for computing discrete logarithms Similar to RSA, the discrete logarithm is an important application of number theory to cryptog- raphy. The discrete logarithm problem is considered to be computationally intractable. That is, no efficient classical algorithm is known for computing discrete logarithms in general. Hence it serves as a basis as modern cryptography. The discrete logarithm problem (DLP) can be considered as the analogue of the ordinary logarithm; but in a finite group. I n number theoretical setu p, the DLP is defined as: given g and h; and a prune modulus p, find r such that g, h (mod p assuming the solutions r exists. Again one can try all such but this is not efficient in general. Pohlig-Hell?nan algorithin is an algorithin for computing discrete logarithms when the modulus p is special. Note in Pohlig-Hellman, one can assume we can factor p 1 efficiently. Here are the questions to be answered in this project