মডুলার গুণনীয় বিপরীত#
সংজ্ঞা#
একটি পূর্ণসংখ্যা $a$-এর মডুলার গুণনীয় বিপরীত হলো এমন একটি পূর্ণসংখ্যা $x$ যেন $a \cdot x$ কোনো মডুলাস $m$-এর জন্য $1$-এর সর্বসম। এটি আনুষ্ঠানিকভাবে লিখতে: আমরা এমন একটি পূর্ণসংখ্যা $x$ খুঁজতে চাই যেন
$$a \cdot x \equiv 1 \mod m.$$আমরা $x$-কে সংক্ষেপে $a^{-1}$ দ্বারাও চিহ্নিত করব।
লক্ষ্য করা উচিত যে মডুলার ইনভার্স সবসময় বিদ্যমান থাকে না। উদাহরণস্বরূপ, মনে করি $m = 4$, $a = 2$। $m$ মডুলোতে সকল সম্ভাব্য মান পরীক্ষা করলে স্পষ্ট হওয়া উচিত যে আমরা উপরের সমীকরণ সিদ্ধ করে এমন $a^{-1}$ খুঁজে পাব না। প্রমাণ করা যায় যে মডুলার ইনভার্স বিদ্যমান যদি এবং কেবল যদি $a$ ও $m$ পরস্পর সহমৌলিক হয় (অর্থাৎ $\gcd(a, m) = 1$)।
এই নিবন্ধে, আমরা মডুলার ইনভার্স বিদ্যমান থাকলে তা খুঁজে বের করার দুটি পদ্ধতি এবং রৈখিক সময়ে সকল সংখ্যার মডুলার ইনভার্স নির্ণয়ের একটি পদ্ধতি উপস্থাপন করব।
এক্সটেন্ডেড ইউক্লিডিয়ান অ্যালগরিদম ব্যবহার করে মডুলার ইনভার্স নির্ণয়#
নিম্নলিখিত সমীকরণটি বিবেচনা করুন (অজানা $x$ ও $y$ সহ):
$$a \cdot x + m \cdot y = 1$$এটি দুটি চলকে একটি রৈখিক ডায়োফ্যান্টাইন সমীকরণ। সংযুক্ত নিবন্ধে দেখানো হয়েছে, যখন $\gcd(a, m) = 1$, তখন সমীকরণটির একটি সমাধান আছে যা এক্সটেন্ডেড ইউক্লিডিয়ান অ্যালগরিদম ব্যবহার করে বের করা যায়। লক্ষ্য করুন যে $\gcd(a, m) = 1$ মডুলার ইনভার্স বিদ্যমান থাকার শর্তও।
এখন, উভয় পক্ষে $m$ মডুলো নিলে, আমরা $m \cdot y$ বাদ দিতে পারি, এবং সমীকরণটি হয়ে যায়:
$$a \cdot x \equiv 1 \mod m$$সুতরাং, $a$-এর মডুলার ইনভার্স হলো $x$।
ইমপ্লিমেন্টেশন নিম্নরূপ:
int x, y;
int g = extended_euclidean(a, m, x, y);
if (g != 1) {
cout << "No solution!";
}
else {
x = (x % m + m) % m;
cout << x << endl;
}লক্ষ্য করুন আমরা x কিভাবে পরিবর্তন করি।
এক্সটেন্ডেড ইউক্লিডিয়ান অ্যালগরিদম থেকে প্রাপ্ত x ঋণাত্মক হতে পারে, তাই x % m-ও ঋণাত্মক হতে পারে, এবং ধনাত্মক করতে আমাদের প্রথমে m যোগ করতে হবে।
মডুলার ইনভার্স নির্ণয়ের আরেকটি পদ্ধতি হলো অয়লারের উপপাদ্য ব্যবহার করা, যা বলে যে $a$ ও $m$ পরস্পর সহমৌলিক হলে নিম্নলিখিত সর্বসমতা সত্য:
$$a^{\phi (m)} \equiv 1 \mod m$$$\phi$ হলো অয়লারের টোশেন্ট ফাংশন। আবারও লক্ষ্য করুন, $a$ ও $m$ পরস্পর সহমৌলিক হওয়াটাও মডুলার ইনভার্স বিদ্যমান থাকার শর্ত ছিল।
যদি $m$ একটি মৌলিক সংখ্যা হয়, তাহলে এটি ফার্মার ক্ষুদ্র উপপাদ্য-এ সরলীকৃত হয়:
$$a^{m - 1} \equiv 1 \mod m$$উপরের সমীকরণের উভয় পক্ষকে $a^{-1}$ দিয়ে গুণ করলে পাই:
- একটি ইচ্ছামতো (তবে সহমৌলিক) মডুলাস $m$-এর জন্য: $a ^ {\phi (m) - 1} \equiv a ^{-1} \mod m$
- একটি মৌলিক মডুলাস $m$-এর জন্য: $a ^ {m - 2} \equiv a ^ {-1} \mod m$
এই ফলাফল থেকে, আমরা সহজেই বাইনারি এক্সপোনেনশিয়েশন অ্যালগরিদম ব্যবহার করে মডুলার ইনভার্স বের করতে পারি, যা $O(\log m)$ সময়ে কাজ করে।
যদিও এই পদ্ধতিটি পূর্ববর্তী অনুচ্ছেদে বর্ণিত পদ্ধতির চেয়ে বুঝতে সহজ, $m$ মৌলিক না হলে আমাদের অয়লারের ফি ফাংশন গণনা করতে হবে, যার জন্য $m$-এর উৎপাদক বিশ্লেষণ প্রয়োজন, যা অত্যন্ত কঠিন হতে পারে। $m$-এর মৌলিক উৎপাদক বিশ্লেষণ জানা থাকলে, এই পদ্ধতির কমপ্লেক্সিটি $O(\log m)$।
## ইউক্লিডিয়ান বিভাজন ব্যবহার করে মৌলিক মডুলির জন্য মডুলার ইনভার্স নির্ণয়একটি মৌলিক মডুলাস $m > a$ দেওয়া আছে (অথবা আমরা ১ ধাপে মডুলো প্রয়োগ করে এটি ছোট করতে পারি), ইউক্লিডিয়ান বিভাজন অনুসারে
$$m = k \cdot a + r$$যেখানে $k = \left\lfloor \frac{m}{a} \right\rfloor$ এবং $r = m \bmod a$, তাহলে
$$ \begin{align*} & \implies & 0 & \equiv k \cdot a + r & \mod m \\ & \iff & r & \equiv -k \cdot a & \mod m \\ & \iff & r \cdot a^{-1} & \equiv -k & \mod m \\ & \iff & a^{-1} & \equiv -k \cdot r^{-1} & \mod m \end{align*} $$লক্ষ্য করুন $m$ মৌলিক না হলে এই যুক্তি ধরে না, কারণ $a^{-1}$-এর অস্তিত্ব সাধারণ ক্ষেত্রে $r^{-1}$-এর অস্তিত্ব নিশ্চিত করে না। এটি দেখতে, উপরের সূত্র দিয়ে $12$ মডুলোতে $5^{-1}$ গণনার চেষ্টা করুন। আমরা $5$-এ পৌঁছাতে চাই, কারণ $5 \cdot 5 \equiv 1 \bmod 12$। তবে, $12 = 2 \cdot 5 + 2$, এবং আমাদের $k=2$ ও $r=2$, যেখানে $2$, $12$ মডুলোতে বিপরীতযোগ্য নয়।
তবে মডুলাস মৌলিক হলে, $0 < a < m$ বিশিষ্ট সকল $a$, $m$ মডুলোতে বিপরীতযোগ্য, এবং আমরা $m$-এর সাপেক্ষে $a$ সংখ্যার মডুলার ইনভার্স গণনার জন্য নিম্নলিখিত রিকার্সিভ ফাংশন (C++-এ) ব্যবহার করতে পারি
int inv(int a) {
return a <= 1 ? a : m - (long long)(m/a) * inv(m % a) % m;
}এই রিকার্সনের সঠিক টাইম কমপ্লেক্সিটি জানা নেই। এটি $O(\frac{\log m}{\log\log m})$ ও $O(m^{\frac{1}{3} - \frac{2}{177} + \epsilon})$-এর মধ্যে কোথাও। দেখুন On the length of Pierce expansions। বাস্তবে এই ইমপ্লিমেন্টেশন দ্রুত, যেমন মডুলাস $10^9 + 7$-এর জন্য এটি সবসময় ৫০ ইটারেশনের কম সময়ে শেষ হবে।
এই সূত্র প্রয়োগ করে, আমরা $[1, m-1]$ রেঞ্জের প্রতিটি সংখ্যার মডুলার ইনভার্সও $O(m)$-তে প্রিকম্পিউট করতে পারি।inv[1] = 1;
for(int a = 2; a < m; ++a)
inv[a] = m - (long long)(m/a) * inv[m%a] % m;$m$ মডুলোতে সংখ্যার অ্যারের জন্য মডুলার ইনভার্স নির্ণয়#
ধরুন আমাদের একটি অ্যারে দেওয়া আছে এবং আমরা এর সকল সংখ্যার মডুলার ইনভার্স বের করতে চাই (সবগুলো বিপরীতযোগ্য)। প্রতিটি সংখ্যার জন্য আলাদাভাবে ইনভার্স গণনা না করে, আমরা ভগ্নাংশটিকে প্রিফিক্স গুণফল (নিজে বাদে) ও সাফিক্স গুণফল (নিজে বাদে) দিয়ে প্রসারিত করতে পারি, এবং শেষে কেবল একটি ইনভার্স গণনা করতে হয়।
$$ \begin{align} x_i^{-1} &= \frac{1}{x_i} = \frac{\overbrace{x_1 \cdot x_2 \cdots x_{i-1}}^{\text{prefix}_{i-1}} \cdot ~1~ \cdot \overbrace{x_{i+1} \cdot x_{i+2} \cdots x_n}^{\text{suffix}_{i+1}}}{x_1 \cdot x_2 \cdots x_{i-1} \cdot x_i \cdot x_{i+1} \cdot x_{i+2} \cdots x_n} \\ &= \text{prefix}_{i-1} \cdot \text{suffix}_{i+1} \cdot \left(x_1 \cdot x_2 \cdots x_n\right)^{-1} \end{align} $$কোডে আমরা একটি প্রিফিক্স গুণফল অ্যারে তৈরি করতে পারি (নিজে বাদে, আইডেন্টিটি এলিমেন্ট থেকে শুরু করে), সকল সংখ্যার গুণফলের মডুলার ইনভার্স গণনা করতে পারি এবং তারপর এটিকে প্রিফিক্স গুণফল ও সাফিক্স গুণফল (নিজে বাদে) দিয়ে গুণ করতে পারি। সাফিক্স গুণফল পেছন থেকে সামনের দিকে ইটারেট করে গণনা করা হয়।
std::vector<int> invs(const std::vector<int> &a, int m) {
int n = a.size();
if (n == 0) return {};
std::vector<int> b(n);
int v = 1;
for (int i = 0; i != n; ++i) {
b[i] = v;
v = static_cast<long long>(v) * a[i] % m;
}
int x, y;
extended_euclidean(v, m, x, y);
x = (x % m + m) % m;
for (int i = n - 1; i >= 0; --i) {
b[i] = static_cast<long long>(x) * b[i] % m;
x = static_cast<long long>(x) * a[i] % m;
}
return b;
}