A simple modular reconstruction conundrum on CRT

39 Views Asked by At

Assume we have two primes $r$ and $s$.

Assume that we have $a =N\bmod r$ and $b=N\bmod s$, then can we find $N\bmod rs$ using CRT?

All explanations I have found say that if we have $rs>N$, then we can find $N$.

My query is what happens if $rs<N$ and $rst>N$ can we still find $N\bmod rs$, $N\bmod st$, $N\bmod tr$? Assume $N\bmod t$ is known at a third prime $t$ and assume $N\bmod r$ and $N\bmod s$ also is known $r$ and $s$ prime

CRT guarantees $N=N\bmod rst$.

That is I want $N$ to be found and without using $N$ find $N\bmod rs$, $N\bmod st$, $N\bmod tr$ so that the $N$ we found agrees with find $N\bmod rs$, $N\bmod st$, $N\bmod tr$ at moduli $rs,st,tr$ respectively

1

There are 1 best solutions below

16
On

Usually, the solution goes this way: find with the Extended Euclidean algorithm coefficients $u$ and $v$ such that $$ur+vs=1,\quad \lvert u\rvert < s,\enspace \lvert v\rvert < r.$$ The solutions are $$N\equiv bru+avs\mod rs.$$ Thus, if you have $N>rs$, you only have to reduce $N$ modulo $rs$.