I want to solve for $s=\frac{(M-x^y)}{r}$ mod $(p-1)$ where I know the values for $M,x,y,p,s$ but don't know $r$. How can I solve for $r$?
I tried to solve for $r$ by trying to compute $r=\frac{(M-x^y)}{s}$ mod $(p-1)$ in Maple but the correct values were not coming up.
Also if anyone know how to do this using any program that can handle large numbers (30-50 digits long), that would be a plus.
You can't simply divide by $s$ on both sides; if $GCD(p-1,s)>1$ then you actually have $r\equiv\frac{M-x^y}{s}\pmod{\frac{p-1}{GCD(p-1,s)}}$. At the same time, that equivalence should give you all solutions.