Modular Inverse
মডুলার বিপরীত
`a`-এর inverse হলো এমন `x` যে `ax ≡ 1 (mod m)`। অস্তিত্ব আছে **কেবল যদি** `gcd(a, m) = 1`।
also: multiplicative inverse
Modular arithmetic-এ ভাগ সরাসরি নেই — তার বদলে inverse দিয়ে গুণ।
অস্তিত্বের শর্ত: a⁻¹ mod m আছে ⟺ gcd(a, m) = 1।
কেন — extended Euclid ax + my = gcd(a,m) দেয়। gcd = 1 হলে
ax + my = 1, অর্থাৎ ax ≡ 1 (mod m)। gcd > 1 হলে বাঁ পাশ
সবসময় gcd-এর গুণিতক, কখনো 1 হবে না।
def inverse(a, m):
g, x, _ = extended_gcd(a % m, m)
if g != 1: raise ValueError(f"{a}-এর inverse নেই mod {m}")
return x % mm মৌলিক হলে 1 থেকে m−1 পর্যন্ত প্রতিটা সংখ্যার inverse
আছে — তখন ℤ/mℤ একটা field। এই কারণেই cryptography-তে
মৌলিক modulus এত পছন্দ।
Fermat’s little theorem থেকে বিকল্প পদ্ধতি: m মৌলিক হলে
a⁻¹ ≡ a^(m−2) (mod m) — modular exponentiation দিয়ে হিসাব করা যায়।
যেখানে লাগে: [[rsa]]-র decryption exponent (d ≡ e⁻¹ mod φ(n)),
Chinese Remainder Theorem, elliptic curve cryptography, আর
error-correcting code।