پرش به محتویات

لگاریتم گسسته

لگاریتم گسسته، عدد صحیح $x$ است که در معادله زیر صدق می‌کند:

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

به ازای اعداد صحیح داده شده $a$، $b$ و $m$.

لگاریتم گسسته همیشه وجود ندارد، برای مثال هیچ جوابی برای $2^x \equiv 3 \pmod 7$ وجود ندارد. شرط ساده‌ای برای تعیین اینکه آیا لگاریتم گسسته وجود دارد یا نه، موجود نیست.

در این مقاله، الگوریتم گام کودک گام غول (Baby-step giant-step) را شرح می‌دهیم که الگوریتمی برای محاسبه لگاریتم گسسته است که در سال ۱۹۷۱ توسط Shanks پیشنهاد شد و دارای پیچیدگی زمانی $O(\sqrt{m})$ است. این یک الگوریتم ملاقات در میانه (meet-in-the-middle) است زیرا از تکنیک تقسیم وظایف به دو نیم استفاده می‌کند.

الگوریتم

معادله زیر را در نظر بگیرید:

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

که در آن $a$ و $m$ نسبت به هم اول هستند.

فرض کنید $x = np - q$، که در آن $n$ یک ثابت از پیش انتخاب شده است (در ادامه نحوه انتخاب $n$ را توضیح خواهیم داد). $p$ به عنوان گام غول (giant step) شناخته می‌شود، زیرا افزایش آن به اندازه یک، $x$ را به اندازه $n$ افزایش می‌دهد. به طور مشابه، $q$ به عنوان گام کودک (baby step) شناخته می‌شود.

بدیهی است که هر عدد $x$ در بازه $[0; m)$ می‌تواند به این شکل نمایش داده شود، که در آن $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).$$

این مسئله را می‌توان با استفاده از روش ملاقات در میانه به صورت زیر حل کرد:

  • $f_1$ را برای تمام آرگومان‌های ممکن $p$ محاسبه کنید. آرایه‌ای از زوج‌های مقدار-آرگومان را مرتب کنید.
  • برای تمام آرگومان‌های ممکن $q$، مقدار $f_2$ را محاسبه کرده و با استفاده از جستجوی دودویی، به دنبال $p$ متناظر در آرایه مرتب‌شده بگردید.

پیچیدگی

می‌توانیم $f_1(p)$ را در $O(\log m)$ با استفاده از الگوریتم توان‌یابی سریع محاسبه کنیم. به طور مشابه برای $f_2(q)$.

در مرحله اول الگوریتم، باید $f_1$ را برای هر آرگومان ممکن $p$ محاسبه کرده و سپس مقادیر را مرتب کنیم. بنابراین، این مرحله دارای پیچیدگی زیر است:

$$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)$$

در مرحله دوم الگوریتم، باید $f_2(q)$ را برای هر آرگومان ممکن $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 یک جواب مناسب برای مسئله پیدا می‌کند. اگر جوابی وجود نداشته باشد، ۱- برمی‌گرداند و در غیر این صورت یکی از جواب‌های ممکن را برمی‌گرداند.

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;
}

در این کد، ما از map کتابخانه استاندارد C++ برای ذخیره مقادیر $f_1$ استفاده کرده‌ایم. در داخل، 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، می‌توانیم از جدول هش (unordered_map در C++) نیز استفاده کنیم که میانگین پیچیدگی زمانی آن برای درج و جستجو $O(1)$ است.

مسائل اغلب کوچکترین $x$ را که در جواب صدق می‌کند، می‌خواهند. می‌توان تمام جواب‌ها را به دست آورد و کوچکترین را انتخاب کرد، یا اولین جواب یافت شده را با استفاده از قضیه اویلر کاهش داد، اما می‌توانیم در مورد ترتیبی که مقادیر را محاسبه می‌کنیم هوشمندانه عمل کنیم و اطمینان حاصل کنیم که اولین جوابی که پیدا می‌کنیم کوچکترین است.

// کوچکترین x را برمی‌گرداند که a ^ x % m = b % m باشد، a و m نسبت به هم اول هستند.
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 نسبت به هم اول نیستند

فرض کنید $g = \gcd(a, m)$ و $g > 1$. واضح است که $a^x \bmod m$ برای هر $x \ge 1$ بر $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$ تعمیم داد.

// کوچکترین x را برمی‌گرداند که 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)$ انجام می‌شود.

مسائل تمرینی

منابع