A digit-serial algorithm for the discrete logarithm modulo 2k

We introduce as our main result a digit-serial residue arithmetic algorithm for computing the discrete logarithm modulo 2^k (dlg). "Digit inheritance" is presented as a fundamental property common to the primitive operations modulo 2^k of addition, multiplication, multiplicative inverse, exponentiation and discrete logarithm. Our main algorithm computes dlg using binary arithmetic with 3 as the logarithmic base and has a critical path containing one modulo 2^k multiplication operation for each of its k iterations. Extensions of the algorithm to other logarithmic bases and computations using digits in a higher radix 2^r are also described.