Chinese Remainder Theorem
চীনা অবশেষ উপপাদ্য
Pairwise coprime modulus-এর একগুচ্ছ congruence-এর একটা অনন্য সমাধান আছে, modulus-দের গুণফলের ভেতরে।
also: CRT
x ≡ a₁ (mod n₁)
x ≡ a₂ (mod n₂)
...nᵢ-রা pairwise coprime হলে একটা অনন্য সমাধান আছে
mod (n₁n₂⋯nₖ)-এ।
উদাহরণ: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
→ x = 23, আর সাধারণ সমাধান 23 + 105k।
অন্তর্জ্ঞান: ছোট modulus-গুলোর ভাগশেষ একসাথে বড় modulus-এ সংখ্যাটার একটা সম্পূর্ণ “স্থানাঙ্ক” দেয়। বড় সংখ্যাকে কয়েকটা ছোট সংখ্যায় ভেঙে ফেলা যায়, আলাদা আলাদা কাজ করা যায়, তারপর জোড়া লাগানো যায়।
CS-এ প্রয়োগ:
- RSA decryption ~৪ গুণ দ্রুত —
mod pআরmod qআলাদা হিসাব করে CRT দিয়ে জোড়া লাগানো। প্রায় সব বাস্তব RSA implementation এটা করে - Residue Number System — বড় সংখ্যার arithmetic সমান্তরালে চালানো, কারণ প্রতিটা residue স্বাধীন
- Secret sharing ও কিছু error-correcting code
- Hash combining — স্বাধীন modulus-এ hash মিলিয়ে সংঘর্ষ কমানো
সতর্কতা: coprime না হলে theorem খাটে না — সমাধান থাকতেও পারে, নাও পারে।