This discusses the discrete log problem and shows how difficult a discrete log equation is to solve and shows a few algorithms for solving them. The DES and AES algorithms were easier to read because they were diagrammed, I think that drawing out the steps is pretty critical to having them sink in.
The three algorithms that were mentioned were Pohlig-Hellman, Baby Step-Giant Step and Index Calculus.
Baby Step-Giant Step seems to be the easiest to understand. You find a^j=ba^(-nk) with 0<j,k < n and that gives you j+nk is the answer. This is only effective for problems with p is less than 10^20. Not as effective as the Index Calculus, which the book says is effective up to p is less than 10^200.
I don't understand the P-H.
I see lots of problems with the primes that are 3 mod 4. First they have problems with factoring, then they have problems with the discrete log. I bet they are related to the Collatz conjecture. And all those other hard problems that haven't been solved yet.
How is it that 4 comes into both factoring and discrete logs?
Come to think of it, 4 is really important in the Collatz conjecture too. Maybe I should look into that.
No comments:
Post a Comment