1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\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 ♦
    Commented Sep 14, 2022 at 13:00

0

Reset to default

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.