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

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

لگاریتم گسسته، اون عدد صحیح $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$ یه عدد ثابته که خودمون انتخابش می‌کنیم (بعداً می‌گم چطوری بهترین مقدار رو براش پیدا کنیم). $p$ رو بهش می‌گیم «گام غول» (giant step)، چون هر یه دونه که بهش اضافه کنیم، $x$ به اندازه‌ی $n$ تا زیاد می‌شه. به همین ترتیب، به $q$ هم می‌گیم «گام کودک» (baby step).

واضحه که هر عدد $x$ توی بازه‌ی $[0; m)$ رو می‌شه به این شکل نوشت، به شرطی که $p$ توی بازه‌ی $[1; \lceil \frac{m}{n} \rceil ]$ و $q$ توی بازه‌ی $[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(p)$ رو حساب می‌کنیم. بعد این زوج‌های (مقدار، آرگومان) یعنی $(f_1(p), p)$ رو توی یه لیست می‌ریزیم و مرتبش می‌کنیم.
  • حالا برای همه‌ی مقدارهای ممکن $q$، میایم $f_2(q)$ رو حساب می‌کنیم و بعد با جستجوی دودویی (binary search) توی اون لیست مرتب شده‌مون می‌گردیم ببینیم آیا مقداری برابر باهاش پیدا می‌کنیم یا نه. اگه پیدا کردیم، یعنی یه $p$ و $q$ پیدا کردیم که با هم جور در میان و مسئله حله!

پیچیدگی

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

توی مرحله اول الگوریتم، باید برای هر $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 همون کار توان‌رسانی به پیمانه $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$ (یعنی $a^{np}$) رو ذخیره کنیم. map در پشت صحنه از یه درخت قرمز-سیاه استفاده می‌کنه. برای همین این کد یه کوچولو از حالتی که خودمون یه آرایه بسازیم و روش جستجوی دودویی بزنیم کندتره، ولی خب نوشتنش خیلی راحت‌تر و تمیزتره.

یه نکته‌ای که باید حواست باشه اینه که این کد فرض می‌کنه $0^0 = 1$. یعنی مثلاً برای معادله‌ی $0^x \equiv 1 \pmod m$ جواب $0$ رو برمی‌گردونه و برای $0^x \equiv 0 \pmod 1$ هم همینطور. این یه قرارداد رایج توی جبره، ولی همه جا قبولش ندارن. بعضی وقتا $0^0$ رو اصلاً تعریف‌نشده در نظر می‌گیرن. اگه با این قرارداد حال نمی‌کنی، باید حالت $a=0$ رو جداگونه مدیریت کنی، مثلاً اینطوری:

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

یه نکته‌ی دیگه: اگه چند تا $p$ مختلف به یه مقدار یکسان برای $f_1$ برسن، map ما فقط یکی‌شون رو نگه می‌داره. اینجا کارمون راه میفته چون فقط دنبال یه جوابیم. ولی اگه لازم بود همه‌ی جواب‌های ممکن رو پیدا کنی، باید map<int, int> رو به یه چیزی مثل map<int, vector<int>> تغییر بدی و مرحله دوم رو هم متناسب باهاش عوض کنی.

یه پیاده‌سازی بهینه‌تر

یه راه برای بهتر کردن کد اینه که از شر توان‌رسانی‌های مکرر خلاص بشیم. چطوری؟ می‌تونیم یه متغیر داشته باشیم که توی هر مرحله از حلقه $q$، در $a$ ضرب بشه و یه متغیر دیگه که توی هر مرحله از حلقه $p$، در $a^n$ ضرب بشه. با این تغییر، پیچیدگی کلی الگوریتم همون می‌مونه، ولی اون عامل $\log$ که به خاطر توان‌رسانی بود حذف می‌شه. تازه، به جای 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$ بخش‌پذیره.

پس اگه $b$ به $g$ بخش‌پذیر نباشه ($g \nmid b$)، اصلاً جوابی برای $x$ وجود نداره. خلاص!

اما اگه $b$ به $g$ بخش‌پذیر باشه ($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} $$

این روند رو اینقدر تکرار می‌کنیم تا ضریب $a$ و پیمانه نسبت به هم اول بشن. بعد مسئله رو با الگوریتم اصلی حل می‌کنیم. الگوریتم گام کودک گام غول رو می‌شه یه کم تغییر داد تا معادله‌ی کلی‌ترِ $ka^{x} \equiv b \pmod m$ رو هم حل کنه.

// کوچکترین 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)$ انجام می‌شه که در مقابل $\sqrt{m}$ ناچیزه.

چند تا مسئله برای تمرین

منابع بیشتر