Discrete logarithm problem is easy in a cyclic group of order a power of two

Question

Let $G=\langle g\rangle$ be a cyclic group of order $2^{k}$ and let $h\in G$. I have read that it is easy to find $\log _{g} h$, but I haven't been able to figure out how. Do you know why this can be done in polynomial time? Do you know of a book where I can find this?

Answer 1

You may find it useful to play around with a toy example, such as the integers modulo a Fermat prime, like $p = 257$.

Since $g$ is a generator of the Group, $h \equiv g^x$ for some unknown exponent $x$. In other words, $\log_gh = x$, and for Groups of order $2^k$, this discrete log is easily computed like so:

Interpret $x$ as a $k$ bit number, i.e. $x = c_02^0 +c_12^1 + c_22^2 + c_32^3 ...+ c_{k}2^{k}$ where the coefficients $c_0, c_1, c_2...c_k \in \{0,1\}$. You can find the value of $c_0$ by raising $g^x$ to the power $2^{k-1}$ modulo $p$. If $c_0=0$ then all the other terms in $x$ are divisble by 2, thus $x=2y$, and so by Euler's totient theorem, $$(g^{2y})^{2^{k-1}}\equiv g^{y2^k} \equiv g^0 \equiv 1 \mod p$$ If however $c_0 = 1$, then raising $g^x$ to the power $2^{k-1}$ mod $p$ will return the result $p-1$. So by looking at the result, you can see directly what the value of $c_0$ is. Now that you have the value of $c_0$, subtract the term $c_02^0$ from $x$ (i.e. multiply $g^x$ by the modular multiplicative inverse of $g^{c_02^0}$).

Now you can find out what the value of $c_1$ is, by using the same approach: raise $g^{x-c_02^0}$ to the power $2^{k-2}$. If $c_1=0$, then all the remaining terms in $x-c_02^0$ are divisible by 4, and so $x-c_02^0 = 4y$ and $(g^{4y})^{2^{k-2}} \equiv g^{y2^k} \equiv 1 \mod p$. If on the other hand $c_1=1$ then again the result will be $p-1$. Subtract the term $c_12^1$ from $x-c_02^0$, and repeat the procedure for $c_2$. Continue until you have discovered all the coefficients for $x$: you now know what $x$ is.