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

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)$$?

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$$.
• It is not really number theory, but simple counting. There are $p-1$ elements in $\mathbb{Z}^*_p$, and when you iterate over them in order, they map to $\mathbb{Z}_H$ in a regular repeating pattern. 1 out of every $H$ of them maps to your target $h$. But $(p-1)/H$ is probably not an integer, hence the ceiling/floor. – Mikero May 20 '20 at 18:38
• Just visualize $p=31$, $H=7$. $\mathbb{Z}_{31}^* = \{1,2,\ldots,30\}$, and reducing them mod 7 gives $1, 2, \ldots, 6, 0, 1, 2, \ldots, 1,2$. So 1 & 2 have 5 preimages and the other numbers have 4 preimages. – Mikero May 20 '20 at 18:41