I'm given three values $s_0,s_1,s_2 \in \mathbb{Z}_m$ that follows the recursion formular $s_{n+1} = as_n+b \mod m$.

I know $m$ and want to calculate $a,b$. It's easy to see that $a=\frac{s_1-s_2}{s_0-s_1}$ however in my case $gcd(s_0-s_1,m)\neq 1$ thus I'm unable calculate the multiplicative inverse of $s_0-s_1 \mod m$.

Is there any other way of doing this without bruteforcing?

  • $\begingroup$ Hint: be rigorous in establishing a relation between $m$, $a$, $s_0-s_1$, and $s_1-s_2$, in order to come with one that holds without assuming $\gcd(s_0-s_1,m)=1$. Then use that if $v$ divides $u$ and $w$ divides $v$, then $v/w$ divides $u$. $\endgroup$
    – fgrieu
    Sep 14, 2022 at 13:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.