(Difficult) I am not sure if I completely understand this, but does the difficulty of discrete logarithms come from the need to factor p-1? I noticed in the example of 7^x = 12 (mod 41) it was necessary to first factor the number 40. In practice, would p-1 we be choosen as a multiple of two large primes, or does it matter if p-1 factors into more than 2 primes?
(Reflective) The Pohlig-Hellman Algorithm reminded me of the p-1 factoring algorithm with RSA. Although I don't completely understand it, it is interesting how p-1 is used to solve for the modular exponentiation mod p, both with RSA and discrete logarithms. The two methods are obviously related, since they both involve modular exponentiation, but after reading this section, computing discrete logs still seems rather foreign compared to the RSA algorithm.
No comments:
Post a Comment