ডিসক্রিট লগারিদম#

ডিসক্রিট লগারিদম হলো এমন একটি পূর্ণসংখ্যা $x$ যা নিম্নলিখিত সমীকরণ পূরণ করে

$$a^x \equiv b \pmod m$$

প্রদত্ত পূর্ণসংখ্যা $a$, $b$ এবং $m$-এর জন্য।

ডিসক্রিট লগারিদম সর্বদা বিদ্যমান থাকে না, উদাহরণস্বরূপ $2^x \equiv 3 \pmod 7$-এর কোনো সমাধান নেই। ডিসক্রিট লগারিদম বিদ্যমান কিনা নির্ধারণ করার কোনো সরল শর্ত নেই।

এই আর্টিকেলে, আমরা বেবি-স্টেপ জায়ান্ট-স্টেপ অ্যালগরিদম বর্ণনা করব, ডিসক্রিট লগারিদম গণনার একটি অ্যালগরিদম যা ১৯৭১ সালে শ্যাংকস প্রস্তাব করেছিলেন, যার টাইম কমপ্লেক্সিটি $O(\sqrt{m})$। এটি একটি মিট-ইন-দ্য-মিডল অ্যালগরিদম কারণ এটি কাজকে অর্ধেকে ভাগ করার কৌশল ব্যবহার করে।

অ্যালগরিদম#

সমীকরণটি বিবেচনা করুন:

$$a^x \equiv b \pmod m,$$

যেখানে $a$ এবং $m$ পরস্পর সহমৌলিক।

ধরি $x = np - q$, যেখানে $n$ একটি পূর্বনির্ধারিত ধ্রুবক (পরে আমরা $n$ কীভাবে নির্বাচন করতে হয় তা বর্ণনা করব)। $p$-কে জায়ান্ট স্টেপ বলা হয়, কারণ এটি এক বৃদ্ধি করলে $x$ $n$ বৃদ্ধি পায়। একইভাবে, $q$-কে বেবি স্টেপ বলা হয়।

স্পষ্টতই, $[0; m)$ ব্যবধানে যেকোনো সংখ্যা $x$ এই ফর্মে উপস্থাপন করা যায়, যেখানে $p \in [1; \lceil \frac{m}{n} \rceil ]$ এবং $q \in [0; n]$।

তাহলে, সমীকরণটি হয়:

$$a^{np - q} \equiv b \pmod m.$$

$a$ এবং $m$ সহমৌলিক এই তথ্য ব্যবহার করে, আমরা পাই:

$$a^{np} \equiv ba^q \pmod m$$

এই নতুন সমীকরণটি সরলীকৃত আকারে লেখা যায়:

$$f_1(p) = f_2(q).$$

এই সমস্যাটি মিট-ইন-দ্য-মিডল পদ্ধতি ব্যবহার করে নিম্নরূপে সমাধান করা যায়:

সকল সম্ভাব্য আর্গুমেন্ট $p$-এর জন্য $f_1$ গণনা করুন। মান-আর্গুমেন্ট জোড়ার অ্যারে সর্ট করুন।
সকল সম্ভাব্য আর্গুমেন্ট $q$-এর জন্য, $f_2$ গণনা করুন এবং বাইনারি সার্চ ব্যবহার করে সর্ট করা অ্যারেতে সংশ্লিষ্ট $p$ খুঁজুন।

কমপ্লেক্সিটি#

আমরা বাইনারি এক্সপোনেনশিয়েশন অ্যালগরিদম ব্যবহার করে $O(\log m)$-এ $f_1(p)$ গণনা করতে পারি। $f_2(q)$-এর জন্যও একইভাবে।

অ্যালগরিদমের প্রথম ধাপে, আমাদের প্রতিটি সম্ভাব্য আর্গুমেন্ট $p$-এর জন্য $f_1$ গণনা করতে হবে এবং তারপর মানগুলো সর্ট করতে হবে। তাই, এই ধাপের কমপ্লেক্সিটি:

$$O\left(\left\lceil \frac{m}{n} \right\rceil \left(\log m + \log \left\lceil \frac{m}{n} \right\rceil \right)\right) = O\left( \left\lceil \frac {m}{n} \right\rceil \log m\right)$$

অ্যালগরিদমের দ্বিতীয় ধাপে, আমাদের প্রতিটি সম্ভাব্য আর্গুমেন্ট $q$-এর জন্য $f_2(q)$ গণনা করতে হবে এবং তারপর $f_1$-এর মানের অ্যারেতে বাইনারি সার্চ করতে হবে, তাই এই ধাপের কমপ্লেক্সিটি:

$$O\left(n \left(\log m + \log \frac{m}{n} \right) \right) = O\left(n \log m\right).$$

এখন, এই দুই কমপ্লেক্সিটি যোগ করলে, আমরা $\log m$ কে $n$ এবং $m/n$-এর যোগফল দ্বারা গুণিত পাই, যা $n = m/n$ হলে ন্যূনতম, অর্থাৎ সর্বোত্তম পারফর্মেন্স অর্জনের জন্য $n$ এমনভাবে বেছে নেওয়া উচিত যাতে:

$$n = \sqrt{m}.$$

তাহলে, অ্যালগরিদমের কমপ্লেক্সিটি হয়:

$$O(\sqrt {m} \log m).$$

ইমপ্লিমেন্টেশন#

সবচেয়ে সরল ইমপ্লিমেন্টেশন#

নিম্নলিখিত কোডে, powmod ফাংশন $a^b \pmod m$ গণনা করে এবং solve ফাংশন সমস্যার একটি সঠিক সমাধান প্রদান করে। কোনো সমাধান না থাকলে এটি $-1$ রিটার্ন করে এবং অন্যথায় সম্ভাব্য সমাধানগুলোর একটি রিটার্ন করে।

int powmod(int a, int b, int m) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * 1ll * a) % m;
        }
        a = (a * 1ll * a) % m;
        b >>= 1;
    }
    return res;
}

int solve(int a, int b, int m) {
    a %= m, b %= m;
    int n = sqrt(m) + 1;
    map<int, int> vals;
    for (int p = 1; p <= n; ++p)
        vals[powmod(a, p * n, m)] = p;
    for (int q = 0; q <= n; ++q) {
        int cur = (powmod(a, q, m) * 1ll * b) % m;
        if (vals.count(cur)) {
            int ans = vals[cur] * n - q;
            return ans;
        }
    }
    return -1;
}

এই কোডে, আমরা $f_1$-এর মানগুলো সংরক্ষণ করতে C++ স্ট্যান্ডার্ড লাইব্রেরি থেকে map ব্যবহার করেছি। অভ্যন্তরীণভাবে, map মান সংরক্ষণ করতে একটি রেড-ব্ল্যাক ট্রি ব্যবহার করে। তাই এই কোড অ্যারে এবং বাইনারি সার্চ ব্যবহারের চেয়ে একটু ধীর, তবে লিখতে অনেক সহজ।

লক্ষ্য করুন যে আমাদের কোড $0^0 = 1$ ধরে নেয়, অর্থাৎ কোড সমীকরণ $0^x \equiv 1 \pmod m$-এর সমাধান হিসেবে $0$ এবং $0^x \equiv 0 \pmod 1$-এর সমাধান হিসেবেও $0$ গণনা করবে। এটি বীজগণিতে একটি প্রায়ই ব্যবহৃত কনভেনশন, তবে এটি সকল ক্ষেত্রে সার্বজনীনভাবে গৃহীত নয়। কখনো কখনো $0^0$ কেবল অসংজ্ঞায়িত। আপনি যদি আমাদের কনভেনশন পছন্দ না করেন, তাহলে $a=0$ কেসটি আলাদাভাবে হ্যান্ডেল করতে হবে:

    if (a == 0)
        return b == 0 ? 1 : -1;

আরেকটি বিষয় লক্ষণীয় যে, একাধিক আর্গুমেন্ট $p$ $f_1$-এর একই মানে ম্যাপ করলে, আমরা শুধু একটি আর্গুমেন্ট সংরক্ষণ করি। এই ক্ষেত্রে এটি কাজ করে কারণ আমরা শুধু একটি সম্ভাব্য সমাধান রিটার্ন করতে চাই। যদি সকল সম্ভাব্য সমাধান রিটার্ন করতে হয়, তাহলে map<int, int> কে map<int, vector<int>>-এ পরিবর্তন করতে হবে। দ্বিতীয় ধাপটিও সেই অনুযায়ী পরিবর্তন করতে হবে।

উন্নত ইমপ্লিমেন্টেশন#

একটি সম্ভাব্য উন্নতি হলো বাইনারি এক্সপোনেনশিয়েশন থেকে মুক্তি পাওয়া। এটি করা যায় একটি ভেরিয়েবল রেখে যা প্রতিবার $q$ বৃদ্ধি করলে $a$ দ্বারা গুণিত হয় এবং অন্য একটি ভেরিয়েবল যা প্রতিবার $p$ বৃদ্ধি করলে $a^n$ দ্বারা গুণিত হয়। এই পরিবর্তনে, অ্যালগরিদমের কমপ্লেক্সিটি একই থাকে, তবে এখন $\log$ ফ্যাক্টরটি শুধুমাত্র map-এর জন্য। map-এর পরিবর্তে, আমরা একটি হ্যাশ টেবিলও ব্যবহার করতে পারি (C++-এ unordered_map) যার গড় টাইম কমপ্লেক্সিটি ইনসার্ট এবং সার্চের জন্য $O(1)$।

সমস্যাগুলো প্রায়ই সমাধান পূরণ করে এমন ন্যূনতম $x$ চায়। সকল উত্তর পেয়ে ন্যূনতমটি নেওয়া সম্ভব, অথবা অয়লারের উপপাদ্য ব্যবহার করে প্রথম পাওয়া উত্তর কমানো সম্ভব, তবে আমরা মান গণনার ক্রম সম্পর্কে চতুর হতে পারি এবং নিশ্চিত করতে পারি যে আমরা প্রথম যে উত্তর পাব সেটিই ন্যূনতম।

// Returns minimum x for which a ^ x % m = b % m, a and m are coprime.
int solve(int a, int b, int m) {
    a %= m, b %= m;
    int n = sqrt(m) + 1;

    int an = 1;
    for (int i = 0; i < n; ++i)
        an = (an * 1ll * a) % m;

    unordered_map<int, int> vals;
    for (int q = 0, cur = b; q <= n; ++q) {
        vals[cur] = q;
        cur = (cur * 1ll * a) % m;
    }

    for (int p = 1, cur = 1; p <= n; ++p) {
        cur = (cur * 1ll * an) % m;
        if (vals.count(cur)) {
            int ans = n * p - vals[cur];
            return ans;
        }
    }
    return -1;
}

unordered_map ব্যবহার করে কমপ্লেক্সিটি $O(\sqrt{m})$।

যখন $a$ এবং $m$ সহমৌলিক নয় { data-toc-label=‘When a and m are not coprime’ }#

ধরি $g = \gcd(a, m)$, এবং $g > 1$। স্পষ্টতই প্রতি $x \ge 1$-এর জন্য $a^x \bmod m$ $g$ দ্বারা বিভাজ্য হবে।

যদি $g \nmid b$ হয়, তাহলে $x$-এর কোনো সমাধান নেই।

যদি $g \mid b$ হয়, ধরি $a = g \alpha, b = g \beta, m = g \nu$।

$$ \begin{aligned} a^x & \equiv b \mod m \\\ (g \alpha) a^{x - 1} & \equiv g \beta \mod g \nu \\\ \alpha a^{x-1} & \equiv \beta \mod \nu \end{aligned} $$

বেবি-স্টেপ জায়ান্ট-স্টেপ অ্যালগরিদম সহজেই $ka^{x} \equiv b \pmod m$ সমীকরণে $x$-এর জন্য সমাধান করতে সম্প্রসারিত করা যায়।

// Returns minimum x for which a ^ x % m = b % m.
int solve(int a, int b, int m) {
    a %= m, b %= m;
    int k = 1, add = 0, g;
    while ((g = gcd(a, m)) > 1) {
        if (b == k)
            return add;
        if (b % g)
            return -1;
        b /= g, m /= g, ++add;
        k = (k * 1ll * a / g) % m;
    }

    int n = sqrt(m) + 1;
    int an = 1;
    for (int i = 0; i < n; ++i)
        an = (an * 1ll * a) % m;

    unordered_map<int, int> vals;
    for (int q = 0, cur = b; q <= n; ++q) {
        vals[cur] = q;
        cur = (cur * 1ll * a) % m;
    }

    for (int p = 1, cur = k; p <= n; ++p) {
        cur = (cur * 1ll * an) % m;
        if (vals.count(cur)) {
            int ans = n * p - vals[cur] + add;
            return ans;
        }
    }
    return -1;
}

টাইম কমপ্লেক্সিটি আগের মতোই $O(\sqrt{m})$ থাকে কারণ সহমৌলিক $a$ এবং $m$-এ প্রাথমিক রিডাকশন $O(\log^2 m)$-এ সম্পন্ন হয়।