Chinese Remainder Theorem: एक रहस्यमयी गणितीय जादू,Cryptography

चाइनीज़ रिमांडर थ्योरम (CRT): सरल व्याख्या और दैनिक उपयोग

क्या आप जानते हैं कि प्राचीन चीनी गणितज्ञों ने पहले ही एक ऐसी विधि विकसित कर दी थी जो आज कंप्यूटर विज्ञान और क्रिप्टोग्राफी में उपयोग की जाती है? हाँ, हम चाइनीज़ रिमांडर थ्योरम (CRT) की बात कर रहे हैं।

🔍 CRT क्या है?

चाइनीज़ रिमांडर थ्योरम कुछ समस्याओं को हल करने में मदद करता है जिसमें एक संख्या एक मॉड्यूलर A (भाग) और एक अवशिष्ट के रूप में दी जाती है।

🤔 सरल व्याख्या:

मान लेते हैं कि एक संख्या x है, ऐसा कि

जब 3 से विभाजित किया जाए, तो अवशिष्ट 2 है।

जब 5 से विभाजित किया जाए, तो अवशिष्ट 3 है।

जब 7 से विभाजित किया जाए, तो अवशिष्ट 2 है।

इस प्रकार, CRT से हम कह सकते हैं कि हम न्यूनतम पा सकते हैं

इसी प्रकार तीन शर्तें:

(धनात्मक पूर्णांक) x को इस तरह से फ़ॉर्म्युलेट किया जा सकता है।

• $x \equiv 2 \pmod{3}$

• $x \equiv 3 \pmod{5}$

• $x \equiv 2 \pmod{7}$

हल:

CRT के अनुसार, चूंकि 3, 5 और 7 आपस में co-prime हैं, तो हम एक unique solution निकाल सकते हैं।

1. $M = 3 × 5 × 7 = 105$

2. अब:

   • $M_1 = 105/3 = 35$

   • $M_2 = 105/5 = 21$

   • $M_3 = 105/7 = 15$

अब, हर $M_i$ के लिए $y_i$ निकालते हैं, जो यह satisfy करे:

$$M_i\cdot y_i\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{m}_i)$$

• $35 \cdot y_1 \equiv 1 \pmod{3}$ → $y_1 = 2$

• $21 \cdot y_2 \equiv 1 \pmod{5}$ → $y_2 = 1$

• $15 \cdot y_3 \equiv 1 \pmod{7}$ → $y_3 = 1$

अब,

$$x = (2 \cdot 35 \cdot 2) + (3 \cdot 21 \cdot 1) + (2 \cdot 15 \cdot 1) = 140 + 63 + 30 = 233$$

अब $x \mod 105 = 233 \mod 105 = 23$

उत्तर: x = 23

कहां काम आता है?

क्रिप्टोग्राफी (Cryptography): RSA जैसे algorithms में

कंप्यूटर सिस्टम्स: Multicore processors में task division

कैलेंडर सिस्टम्स: विभिन्न तिथियों का मिलान करने में

सिग्नल प्रोसेसिंग: Modular arithmetic के उपयोग में

🧠 टिप्स CRT को याद रखने के लिए:

मॉड्यूलस आपस में co-prime होने चाहिए

हर remainder का अलग हिस्सा निकाला जाता है

अंत में सभी हिस्सों को जोड़कर बड़े मॉड्यूल से mod लिया जाता है