Resolución de la ecuación lineal mod m

Question

Estoy viendo clases de criptografía porque quiero entender las matemáticas que hay detrás del algoritmo de bitcoin. Esto es un hobby, pero estoy teniendo un brainfart ver esta parte de la conferencia :

Las ecuaciones son:

$$ S_2 = AS_1 + B \mod m $$

$$ S_3 = AS_2 + B \mod m $$

Los resolvió y consiguió:

$$ A = (S_2 - S_3)(S_1 - S_2)^{-1} \mod m $$

$$ B = S_2 - S_1(S_2 - S_3)(S_1 - S_2)^{-1} \mod m $$

Pude resolver para A y llegar al mismo resultado pero no para B, ¿Cómo llegó a la ecuación resultante para B? Veo que A se introdujo en la primera ecuación, pero no pude llegar al mismo resultado.

Answer 1

Restando la segunda congruencia de la primera, obtenemos $$ S_3-S_2\equiv AS_2-AS_1\equiv A(S_2-S_1)\pmod m, $$ de donde $A\equiv(S_3-S_2)(S_2-S_1)^{-1}\pmod m$ (siempre que $S_2-S_1$ es invertible, módulo $m$ ).

Entonces la primera ecuación puede reescribirse como $B\equiv S_2-AS_1\mod m$ y sustituyendo $A$ la expresión que acabamos de encontrar antes, $$ B\equiv S_2-S_1(S_3-S_2)(S_2-S_1)^{-1}\pmod m $$