I am working on the following exercise:
$1)$ Fix $x \in \mathbb{Z}_n$ and randomly (u.i.d.) chosse $r_1,r_2,\ldots,r_q \in \mathbb{Z}_n$. Show that when $q$ is chosen as $q = \lfloor \sqrt{2n} \rfloor$ the probability $p$ that there exists $i$ and $j$ such that $r_i = x + r_j \bmod n$ is at least $p = 0.6$.
$2)$ Let $p$ be a prime and $g \in \mathbb{Z}_{p}^{*}$ be a primitive root of $\mathbb{Z}_{p}^{*}$. Show that one can find in $\mathbb{Z}_{p}^{*}$ the discrete logarithm of $X$ to base $g$, if one can find $r$ and $s$ with $$g^r = Xg^s \bmod p$$
Use this and part $1)$ to find an algorithm that solves in $\mathcal{O}(\sqrt{n}) $ steps the discrete logarithm probelm with high probability.
Let us assume that $1)$ is true.
The first claim of $2)$ should follow by observing:
$$g^r \cdot g^{-s} = g^{r-s} = X \bmod p$$
But I do not know how to formulate the sought algorithm. Could you help me with that?