মডুলার এরিথমেটিক

১ · Congruence — "ক্লক এরিথমেটিক"

CongruenceCongruence Modulo nদুটি পূর্ণসংখ্যা $a,b$ একে অপরের congruent মডুলো $n$, লেখা হয় $a \equiv b \pmod n$, যদি $n$ তাদের পার্থক্য $(a-b)$-কে ভাগ করে — সমতুল্যভাবে, $n$ দিয়ে ভাগ করলে দুজনের ভাগশেষ একই হয়। আমাদের প্রতিদিনের ঘড়ির মধ্যেই লুকিয়ে আছে। ঘড়িতে $13$টা মানে $1$টা — কারণ $13 \equiv 1 \pmod{12}$।

$$a \equiv b \pmod{n} \iff n \mid (a-b)$$

যেমন $17 \equiv 5 \pmod{12}$, কারণ $17-5=12$ এবং $12 \mid 12$। সমতুল্যভাবে, $17$ ও $5$-কে $12$ দিয়ে ভাগ করলে দুজনেরই ভাগশেষ $5$।

২ · দ্রুত মডুলার এক্সপোনেনশিয়েশন (Repeated Squaring)

RSA-এর মতো ক্রিপ্টোগ্রাফিক সিস্টেমে প্রায়ই $a^e \bmod n$ গণনা করতে হয় যেখানে $e$ হতে পারে শত শত বিট লম্বা। $a^e$ প্রথমে সরাসরি গণনা করে তারপর $\bmod n$ নেওয়া অসম্ভব — সংখ্যাটি এত বিশাল হয়ে যাবে যে কোনো কম্পিউটারের মেমরিতেও ধরবে না। সমাধান: প্রতিটি ধাপেই মডুলো নিয়ে নেওয়া, কখনো সংখ্যাকে বড় হতে না দেওয়া।

কৌশলটি $e$-এর বাইনারি প্রতিনিধিত্ব-এর উপর ভিত্তি করে — একে "square-and-multiply" বলা হয়: প্রতি ধাপে ফলাফল বর্গ (square) করা হয় এবং $e$-এর সেই বিট $1$ হলে অতিরিক্ত একবার $a$ দিয়ে গুণ করা হয়, প্রতিটি ধাপে $\bmod n$ নিয়ে। ফলে ধাপের সংখ্যা $e$-এর সমানুপাতিক নয় — মাত্র $O(\log e)$।

# pow(base, exp, mod) হলো Python-এর বিল্ট-ইন দ্রুত মডুলার এক্সপোনেনশিয়েশন —
# এটি অভ্যন্তরীণভাবেই repeated squaring ব্যবহার করে, O(log exp) সময়ে

result = pow(7, 128, 13)
print("7^128 mod 13 =", result)

# তুলনা করুন: সরাসরি 7**128 গণনা করলে একটি বিশাল সংখ্যা হতো,
# কিন্তু pow(7,128,13) সবসময় ছোট, দ্রুত থাকে
print("7**128 কত ডিজিট লম্বা?", len(str(7**128)), "ডিজিট — কিন্তু mod নিলে মাত্র একটি ছোট সংখ্যা!")

# মডুলার ইনভার্স: pow(a, -1, n) — Python 3.8+
a, n = 7, 13
inv = pow(a, -1, n)
print(f"{a}^(-1) mod {n} =", inv)
print("যাচাই: (a * a⁻¹) mod n == 1 ?", (a * inv) % n == 1)

৩ · মডুলার ইনভার্স

একটি সংখ্যা $a$-এর মডুলার ইনভার্স মডুলো $n$ হলো এমন একটি সংখ্যা $a^{-1}$ যেন —

$$a \cdot a^{-1} \equiv 1 \pmod{n}$$

সাধারণ ভগ্নাংশে $a^{-1} = 1/a$, কিন্তু মডুলার জগতে ভাগ বলে সরাসরি কিছু নেই — তার বদলে "গুণিতক ইনভার্স" দিয়ে কাজ চালানো হয়। গুরুত্বপূর্ণ শর্ত: $a^{-1} \bmod n$-এর অস্তিত্ব থাকে শুধু তখনই যখন $\gcd(a,n)=1$ (অর্থাৎ $a$ ও $n$ coprime, L25 থেকে)। এই ইনভার্স বের করা হয় L25-এর Extended Euclidean Algorithm দিয়ে — কারণ $\gcd(a,n)=1$ হলে Bézout's Identity থেকে এমন $x,y$ পাওয়া যায় যেন $ax+ny=1$, অর্থাৎ $ax \equiv 1 \pmod n$ — সুতরাং $x$-ই হলো কাঙ্ক্ষিত মডুলার ইনভার্স।