Recovering the random number r
At first glance

$r = s^{-1} (M - a^y) \bmod p-1$

would appear to be what you're looking for.

If $s$ isn't invertable modulo $p-1$, then you can work around this by working with the factors of $p-1$; in this case, $p-1 = uv$ where $s$ is a multiple of $u$ and $s$ is relatively prime to $v$.

So, we can solve:

$r_v = s^{-1} (M - a^y) \bmod v$

and so we have:

$r = r_v + kv$

for some integer $k$; if you know $y_1 = g^r \bmod p$, then you can recover the correct $k$ in $O( \sqrt{u})$ time.