Κινέζικο Θεώρημα Υπολοίπων (CRT): Από τη Θεωρία στον Αλγόριθμο

Το CRT λύνει ταυτόχρονα πολλά συστήματα υπολοίπων και, όταν τα μέτρα είναι ανά δύο πρώτα, εγγυάται μοναδική λύση modulo το γινόμενό τους.

Διατύπωση

Έστω ακέραια μέτρα $m_1,\dots,m_k$ με $\gcd(m_i,m_j)=1$ για κάθε $i\ne j$. Για οποιαδήποτε υπόλοιπα $a_1,\dots,a_k$ υπάρχει μοναδικό $x\pmod{M}$, όπου

$$M=\prod _{i=1}^k{m}_i,$$

τέτοιο ώστε

$$x\equiv a_i(\mathrm{m}\mathrm{o}\mathrm{d}{m}_i)(i=1,\dots ,k)\mathrm{.}$$

Δηλαδή όλες οι λύσεις είναι της μορφής $x\equiv x_0\pmod{M}$ για ένα και μόνο $x_0\in\{0,1,\dots,M-1\}$.

Αλγοριθμική κατασκευή της λύσης

Θέσε $M=\prod_{i=1}^k m_i$ και $M_i=M/m_i$. Βρες για κάθε $i$ έναν αντίστροφο $N_i$ του $M_i$ modulo $m_i$:

$$M_i{N}_i\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{m}_i)(\mu \epsilon \; \epsilon \kappa \tau \epsilon \tau \alpha \mu έ\nu o\; {\rm E}\upsilon \kappa \lambda \epsilon ί\delta \epsilon \iota o).$$

Τότε μία λύση είναι

$$x\equiv \sum _{i=1}^k{a}_i{M}_i{N}_i(\mathrm{m}\mathrm{o}\mathrm{d}M)\mathrm{.}$$

Παράδειγμα

Λύσε

$$x\equiv2\pmod{3},\qquad x\equiv3\pmod{5},\qquad x\equiv2\pmod{7}.$$

Έχουμε $M=3\cdot5\cdot7=105$.

$M_1=35\equiv 2 \pmod{3}\ \Rightarrow\ N_1=2$

$M_2=21\equiv 1 \pmod{5}\ \Rightarrow\ N_2=1$

$M_3=15\equiv 1 \pmod{7}\ \Rightarrow\ N_3=1$

Άρα

$$x\equiv 2\cdot 35\cdot 2+3\cdot 21\cdot 1+2\cdot 15\cdot 1=140+63+30=233\equiv \boxed{{\displaystyle 23}}(\mathrm{m}\mathrm{o}\mathrm{d}105)\mathrm{.}$$

Γενική λύση: $x=23+105t,\ t\in\mathbb{Z}$.

Αν τα μέτρα δεν είναι ανά δύο πρώτα

Το σύστημα $x\equiv a_i\pmod{m_i}$ έχει λύση αν και μόνο αν για όλα τα ζεύγη $i,j$ ισχύει

$$a_i\equiv a_j(\mathrm{m}\mathrm{o}\mathrm{d}\gcd (m_i,m_j))\mathrm{.}$$

Τότε οι λύσεις είναι μοναδικές modulo $\operatorname{lcm}(m_1,\dots,m_k)$.

Εφαρμογές

• Συγχρονισμός ρολογιών/ημερολογίων

• Υπολογισμοί με μεγάλα ακέραια (διάσπαση σε μικρότερα moduli)

• Επιτάχυνση αποκρυπτογράφησης RSA με CRT

• Hashing βασισμένο σε υπολείμματα

• Αλγόριθμος Garner για σταδιακή ανακατασκευή αριθμών από υπολείμματα