1
$\begingroup$

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)

$\endgroup$
  • 2
    $\begingroup$ Why doesn't CRT suffice? $\endgroup$ – Bill Dubuque Aug 9 at 19:07
  • $\begingroup$ It suffice and works well, but it is little involved $\endgroup$ – Mendi Barel Aug 9 at 19:13
  • $\begingroup$ We want to find x. So we know $x \equiv 11 \pmod {13} $ Then $x = 13k + 11$ for some $k$. Plug this in into the equation $x \equiv 9 \pmod {11}$ to get $13 k + 11 \equiv 9 \pmod{11}$ $13k \equiv -2 \equiv 9 \pmod{11} \Rightarrow 2k \equiv 9 \pmod{11} \Rightarrow k \equiv 10 \pmod{11}$. So $x$ is now $13(11p + 10) + 11$ for some integer $p$. Now plug this into another equation and keep going until you get $x = 1571 + 30030 * q$ $ $ for any integer $q$ $\endgroup$ – Francisco José Letterio Aug 9 at 19:18
  • $\begingroup$ Probably because you don't know optimizations. Are you solving them all-at-once or stepwise, two-at-a-time (e.g.in prior comment). $\endgroup$ – Bill Dubuque Aug 9 at 19:20
  • $\begingroup$ we can use that it's odd, to sieve a lot out. but that's mostly CRT. $\endgroup$ – Roddy MacPhee Aug 9 at 19:32
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Can you write function in matlab that solve the problem for any R length and value? Input should be R only. first line should be P=primes(length(R)). $\endgroup$ – Mendi Barel Aug 9 at 20:35
  • $\begingroup$ @MendiBarel Yes, that could be done (I implemented something similar in Macsyma long ago). $\endgroup$ – Bill Dubuque Aug 9 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.