In a Schnorr group as used for DSA, of prime modulus $p$, prime order $q$, generator $g$ (with $p/g$ small), how can we efficiently exhibit an $x$ with $0<x<q$ such that $g^x\bmod p<p/k$, for sizable $k$ but $k\ll\sqrt q$ ?
I see that for small $k$, it is enough to try incremental values of $x$ until finding an $x$ that fits, with expected cost $O(k)$ modular multiplications in $\mathbb Z_p^*$. Is there better?
Assume $p$ is an $l$-bit prime; $q$ is an $n$-bit prime with $q$ dividing $p-1$; and $g=h^{(p-1)/q}$ for some (random?) $h$ in $\mathbb Z_p^*$. For concrete values, assume $l\approx1024$, $n\approx160$, $k\approx2^{64}$.
Update: I'm expecting the problem to be hard, and thus that the more difficult problem of exhibiting $x$ with $g^x\bmod p$ in a range of width $p/k$ must be hard.