Note on the baby-step giant-step algorithm_澳门皇冠体育,皇冠足球比分

haakja
2020-10-13T20:26:40.706Z
type:structured-message
www.uio.no

During today's lecture (Lecture 8, October 13), a student asked whether the generic DLOG algorithms are guaranteed to find the discrete logarithm. I said that the Pollard-rho algorithm is probabilistic and has a chance of failure. However, I don't think I actually answered the question for the baby-step giant-step algorithm! So here it is: baby-step giant step is guaranteed to succeed. I've written a 0.5-page note describing the baby-step giant step in a little more detail here. The included figure should explain why it always succeeds.