4
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I must be missing something. If $G$ is a group and $g,h\in G$, what does $g^{h}$ mean? $\endgroup$ – Howard Apr 2 '16 at 14:38
  • $\begingroup$ @Howard - I think I initially misunderstood precisely what you were asking, but have clarified my answer. Let me know if this is still not clear. $\endgroup$ – J.D. Apr 2 '16 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.