I have a question that intrigue me:
Given primes and some reminder vector
P=primes(13)=[2 3 5 7 11 13]
R=[1 2 1 3 9 11] (R=mod(1571,P))
What option do i have to reconstruct 1571 from R?
I already know about CRT.
Is there any other way? (assumming that direct brute force search is not practical)
It's easy if you solve them stepwise - two-at-a-time.
$x\equiv -2\, \bmod 11\, \&\, 13 \iff x\equiv -2\pmod{\!143}\ $ by CCRT = Constant case CRT. Similarly
$\ x \equiv\ 1\,\bmod\ 2\ \, \&\ \ 5\ \iff\, x\ \equiv\ 1\ \pmod{\!10}.\ $ Solving them pairwise we obtain:
$\!\!\bmod \color{#c00}{10}\!:\,\ 1\equiv x\equiv -2+143\,\color{#c00}i\equiv -2+3i\iff 3i\equiv 3\iff \color{#c00}{i\equiv 1}$
Therefore $\ x = -2+143(\color{#c00}{1\!+\!10j}) = \color{#0a0}{141 + 1430j}$
$\!\!\bmod 7\!:\,\ 3\equiv x\equiv\color{#0a0}{ 1+2j}\iff 2j\equiv 2\iff j\equiv 1$
Therefore $\,x \equiv 141+1430(1\!+\!7k) = \color{#90f}{1571 + 10010k}$
$\!\!\bmod 3\!:\,\ 2\equiv x\equiv\color{#90f}{ 2+2k}\iff k = 0\iff k =3n$
Therefore $\,x \equiv 1571+ 30030n.\,$ Just a couple minutes mental arithmetic (with practice).