On getting beyond LSB in discrete log

Question

In discrete log we employ sophie germain primes $p=2q+1$ where $q$ is a prime.

Then we know least significant bit $x_0$ in $$g^{2x+x_0}=h\bmod p$$ where $2x+x_0$ is discrete logarithm of known $h\bmod p$ with respect to known generator $g$.

1. Suppose $g^2=r\bmod p$ then why cannot I reduce the problem to $$r^{x}=hg^{-x_0}\bmod p$$ and let $x=2x'+x'_{0}$ where $x'_0$ is lsb of $x$ and recursive solve the problem of finding $2x+x_0$ which is discrete log of $h\bmod p$ with respect to generator $g$?

2. Suppose I know $x_0$ in $g^{3x+x_0}=h\bmod p$ where $x_0\in\{0,1,2\}$ holds (that is if it were easy to solve for the last ternary digit of discrete logarithm when $p=2q+1$ would the problem be any easier?

Answer 1

If $p = 2q+1$ where $q$ is prime, and then we can efficiently solve for $x_0 \in \{0, 1\}$ for $g^{2x+x_0} = h \pmod p$, if $g$ is a generator.

This is true; this is a special case of the observation "if $g$ has order $a \times b$ with $b$ small, then if $g^y = h$, then we can find $y \bmod b$ quickly (specifically, in $O(\sqrt{b})$ time).

As $g$ is a generator for the entire group, it has order $2q$, and so we can find $y \bmod 2$ quickly (or, as you put it, find $x_0$ where $y = 2x + x_0$)

Suppose $g^2 = r$, then why cannot I reduce the problem to $r^x = hg^{-x_0} \pmod p$

Well, I suppose you could, but solving that would be as difficult as the DLog problem (actually, that's provable; given an Oracle to do that, you can solve the entire DLog problem). The previous observation doesn't help you solve this problem; $r$ has order $q$, which is a prime; it doesn't provide any magic ways to compute $x \bmod 2$; the best it can do is find $x \bmod q$ in $O(\sqrt{q})$ time, and we have more efficient ways than that.

Suppose I know $x_0$ in $g^{3x+x_0} = h \pmod p$, which $x \in \{ 0, 1, 2 \}$, would that help.

Yes, if you had an Oracle that could find $y \bmod 3$, then you could efficiently solve the DLog problem. That said, we don't know any way to do that efficiently (assuming that the order of the group wasn't a multiple of 3).