Mapping a value $g^x \bmod p$ to a small interval $[1...H]$

Question

My question is in $\mathbb{Z}_p^{*}$ context, where $p=q\cdot k+1$ for two primes $p,q$ and $k \in \mathbb{Z}$; $g$ is the generator of the subgroup $G_q$ of $\mathbb{Z}_p^{*}$, of order $q$.

Let's consider a small $H$ (e.g. $H=1024$) and a specific $h \in \mathbb{Z}_p$, with $0 < h < H$, and we randomly choose $g \in \mathbb{Z}_q$: is it true (I hope it is) that it is easy to find a $x$ such that $h \equiv (g^x \bmod p) \bmod H$?

My concern is: is it possible to create a mapping from a randomly chosen $g^x \bmod p$ that can be mapped to a target (desired) value $h$ in a small range, such that we can find it easily, e.g., in $\mathcal{O}(H)$?

Answer 1

Just sample a random $x$, and $[(g^x \bmod p) \bmod H]$ will equal your target value $h$ with probability $1/H$. After trying $O(H)$ candidates you will find a preimage.

Fine print: Technically speaking, the probability isn't exactly $1/H$. Each $h \in \mathbb{Z}_H$ has either $\lfloor \frac{p-1}{H} \rfloor$ or $\lceil \frac{p-1}{H} \rceil$ preimages under the mapping $a \in \mathbb{Z}^*_p \mapsto (a \bmod H)$. So the probability of hitting your target $h$, when you choose a random $a \in \mathbb{Z}_p^*$, is $\lfloor \frac{p-1}{H} \rfloor/(p-1)$ for some $h$'s and $\lceil \frac{p-1}{H} \rceil/(p-1)$ for others. But if $p$ is exponentially large (as I suspect it is here since you're talking about discrete logs), then this probability is negligibly close to $1/H$.