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

توان رسانی دودویی از طریق تجزیه

مسئله محاسبه $ax^y \pmod{2^d}$ را به ازای اعداد صحیح $a$، $x$، $y$ و $d \geq 3$ در نظر بگیرید، که در آن $x$ فرد است.

الگوریتم زیر امکان حل این مسئله را با $O(d)$ عمل جمع و عملیات دودویی و تنها یک عمل ضرب در $y$ فراهم می‌کند.

به دلیل ساختار گروه ضربی به پیمانه $2^d$، هر عدد $x$ که در شرط $x \equiv 1 \pmod 4$ صدق کند، می‌تواند به صورت زیر نمایش داده شود:

$$ x \equiv b^{L(x)} \pmod{2^d}, $$

که در آن $b \equiv 5 \pmod 8$ است. بدون از دست دادن کلیت مسئله، فرض می‌کنیم که $x \equiv 1 \pmod 4$ است، زیرا می‌توانیم حالت $x \equiv 3 \pmod 4$ را با جایگزینی $x \mapsto -x$ و $a \mapsto (-1)^{y} a$ به حالت $x \equiv 1 \pmod 4$ کاهش دهیم. با این تعریف، $ax^y$ به صورت زیر نمایش داده می‌شود:

$$ a x^y \equiv a b^{yL(x)} \pmod{2^d}. $$

ایده اصلی الگوریتم، ساده‌سازی محاسبه $L(x)$ و $b^{y L(x)}$ با استفاده از این واقعیت است که ما در پیمانه $2^d$ کار می‌کنیم. به دلایلی که بعداً مشخص خواهد شد، ما به جای $L(x)$ با $4L(x)$ کار خواهیم کرد، اما این مقدار به پیمانه $2^d$ به جای $2^{d-2}$ گرفته می‌شود.

در این مقاله، پیاده‌سازی برای اعداد صحیح $32$ بیتی را بررسی می‌کنیم. فرض کنید:

  • mbin_log_32(r, x) تابعی باشد که $r+4L(x) \pmod{2^d}$ را محاسبه می‌کند؛
  • mbin_exp_32(r, x) تابعی باشد که $r b^{\frac{x}{4}} \pmod{2^d}$ را محاسبه می‌کند؛
  • mbin_power_odd_32(a, x, y) تابعی باشد که $ax^y \pmod{2^d}$ را محاسبه می‌کند.

در این صورت، mbin_power_odd_32 به صورت زیر پیاده‌سازی می‌شود:

uint32_t mbin_power_odd_32(uint32_t rem, uint32_t base, uint32_t exp) {
    if (base & 2) {
        /* مقسوم علیه منفی در نظر گرفته می‌شود */
        base = -base;
        /* بررسی اینکه آیا نتیجه باید منفی باشد */
        if (exp & 1) {
            rem = -rem;
        }
    }
    return (mbin_exp_32(rem, mbin_log_32(0, base) * exp));
}

محاسبه 4L(x) از روی x

فرض کنید $x$ یک عدد فرد باشد به طوری که $x \equiv 1 \pmod 4$. می‌توان آن را به صورت زیر نمایش داد:

$$ x \equiv (2^{a_1}+1)\dots(2^{a_k}+1) \pmod{2^d}, $$

که در آن $1 < a_1 < \dots < a_k < d$ است. در اینجا $L(\cdot)$ برای هر ضریب خوش‌تعریف است، زیرا همگی به پیمانه $4$ برابر با $1$ هستند. بنابراین،

$$ 4L(x) \equiv 4L(2^{a_1}+1)+\dots+4L(2^{a_k}+1) \pmod{2^{d}}. $$

بنابراین، اگر ما $t_n = 4L(2^n+1)$ را برای تمام $n$هایی که در شرط $1 < n < d$ صدق می‌کنند از پیش محاسبه کنیم، قادر خواهیم بود $4L(x)$ را برای هر عدد $x$ محاسبه کنیم.

برای اعداد صحیح ۳۲ بیتی، می‌توانیم از جدول زیر استفاده کنیم:

const uint32_t mbin_log_32_table[32] = {
    0x00000000, 0x00000000, 0xd3cfd984, 0x9ee62e18,
    0xe83d9070, 0xb59e81e0, 0xa17407c0, 0xce601f80,
    0xf4807f00, 0xe701fe00, 0xbe07fc00, 0xfc1ff800,
    0xf87ff000, 0xf1ffe000, 0xe7ffc000, 0xdfff8000,
    0xffff0000, 0xfffe0000, 0xfffc0000, 0xfff80000,
    0xfff00000, 0xffe00000, 0xffc00000, 0xff800000,
    0xff000000, 0xfe000000, 0xfc000000, 0xf8000000,
    0xf0000000, 0xe0000000, 0xc0000000, 0x80000000,
};

در عمل، رویکردی کمی متفاوت از آنچه در بالا توضیح داده شد استفاده می‌شود. به جای یافتن تجزیه برای $x$، ما به طور متوالی $x$ را در $2^n+1$ ضرب می‌کنیم تا زمانی که آن را به $1$ به پیمانه $2^d$ تبدیل کنیم. به این ترتیب، ما نمایش $x^{-1}$ را پیدا خواهیم کرد، یعنی:

$$ x (2^{a_1}+1)\dots(2^{a_k}+1) \equiv 1 \pmod {2^d}. $$

برای انجام این کار، ما روی $n$ به طوری که $1 < n < d$ است، تکرار می‌کنیم. اگر بیت $n$-امِ $x$ فعلی یک باشد، ما $x$ را در $2^n+1$ ضرب می‌کنیم، که این کار در C++ به راحتی با x = x + (x << n) انجام می‌شود. این کار بیت‌های کمتر از $n$ را تغییر نمی‌دهد، اما بیت $n$-ام را صفر می‌کند، زیرا $x$ فرد است.

با در نظر گرفتن همه این موارد، تابع mbin_log_32(r, x) به صورت زیر پیاده‌سازی می‌شود:

uint32_t mbin_log_32(uint32_t r, uint32_t x) {
    uint8_t n;

    for (n = 2; n < 32; n++) {
        if (x & (1 << n)) {
            x = x + (x << n);
            r -= mbin_log_32_table[n];
        }
    }

    return r;
}

توجه داشته باشید که $4L(x) = -4L(x^{-1})$، بنابراین به جای جمع کردن $4L(2^n+1)$، آن را از $r$ که در ابتدا برابر با $0$ است، کم می‌کنیم.

محاسبه x از روی 4L(x)

توجه داشته باشید که برای $k \geq 1$ رابطه زیر برقرار است:

$$ (a 2^{k}+1)^2 = a^2 2^{2k} +a 2^{k+1}+1 = b2^{k+1}+1, $$

که از آن (با به توان رساندن مکرر) می‌توان نتیجه گرفت که

$$ (2^a+1)^{2^b} \equiv 1 \pmod{2^{a+b}}. $$

با اعمال این نتیجه، می‌توان نتیجه گرفت که مرتبه ضربی $2^n+1$ مقسوم‌علیهی از $2^{d-n}$ است.

این به نوبه خود به این معناست که $L(2^n+1)$ باید بر $2^{n}$ بخش‌پذیر باشد، زیرا مرتبه $b$ برابر $2^{d-2}$ است و مرتبه $b^y$ برابر $2^{d-2-v}$ است، که در آن $2^v$ بزرگترین توان ۲ است که $y$ را عاد می‌کند، بنابراین لازم است که:

$$ 2^{d-k} \equiv 0 \pmod{2^{d-2-v}}, $$

بنابراین $v$ باید بزرگتر یا مساوی $k-2$ باشد. این موضوع کمی ناخوشایند است و برای رفع این مشکل، در ابتدا گفتیم که $L(x)$ را در $4$ ضرب می‌کنیم. اکنون اگر $4L(x)$ را بدانیم، می‌توانیم با بررسی متوالی بیت‌های آن، آن را به طور یکتا به مجموعی از جملات $4L(2^n+1)$ تجزیه کنیم. اگر بیت $n$-ام برابر $1$ باشد، نتیجه را در $2^n+1$ ضرب خواهیم کرد و $4L(x)$ فعلی را به اندازه $4L(2^n+1)$ کاهش می‌دهیم.

بنابراین، mbin_exp_32 به صورت زیر پیاده‌سازی می‌شود:

uint32_t mbin_exp_32(uint32_t r, uint32_t x) {
    uint8_t n;

    for (n = 2; n < 32; n++) {
        if (x & (1 << n)) {
            r = r + (r << n);
            x -= mbin_log_32_table[n];
        }
    }

    return r;
}

بهینه‌سازی‌های بیشتر

اگر توجه داشته باشید که $4L(2^{d-1}+1)=2^{d-1}$ و اینکه برای $2n \geq d$ رابطه زیر برقرار است، می‌توان تعداد تکرارها را به نصف کاهش داد:

$$ (2^n+1)^2 \equiv 2^{2n} + 2^{n+1}+1 \equiv 2^{n+1}+1 \pmod{2^d}, $$

که به ما اجازه می‌دهد نتیجه بگیریم که برای $2n \geq d$ رابطه $4L(2^n+1)=2^n$ برقرار است. بنابراین، می‌توانید الگوریتم را با اجرای حلقه تنها تا $\frac{d}{2}$ ساده کرده و سپس با استفاده از واقعیت فوق، بخش باقی‌مانده را با عملیات بیتی محاسبه کنید:

uint32_t mbin_log_32(uint32_t r, uint32_t x) {
    uint8_t n;

    for (n = 2; n != 16; n++) {
        if (x & (1 << n)) {
            x = x + (x << n);
            r -= mbin_log_32_table[n];
        }
    }

    r -= (x & 0xFFFF0000);

    return r;
}

uint32_t mbin_exp_32(uint32_t r, uint32_t x) {
    uint8_t n;

    for (n = 2; n != 16; n++) {
        if (x & (1 << n)) {
            r = r + (r << n);
            x -= mbin_log_32_table[n];
        }
    }

    r *= 1 - (x & 0xFFFF0000);

    return r;
}

محاسبه جدول لگاریتم

برای محاسبه جدول لگاریتم، می‌توان الگوریتم Pohlig–Hellman را برای حالتی که پیمانه توانی از ۲ است، تغییر داد.

وظیفه اصلی ما در اینجا محاسبه $x$ به طوری است که $g^x \equiv y \pmod{2^d}$، که در آن $g=5$ و $y$ عددی از نوع $2^n+1$ است.

با $k$ بار به توان دو رساندن طرفین، به رابطه زیر می‌رسیم:

$$ g^{2^k x} \equiv y^{2^k} \pmod{2^d}. $$

توجه داشته باشید که مرتبه $g$ بزرگتر از $2^d$ نیست (در واقع، بزرگتر از $2^{d-2}$ نیست، اما برای راحتی کار با $2^d$ ادامه می‌دهیم)، بنابراین با استفاده از $k=d-1$ در سمت چپ یا $g^1$ یا $g^0$ را خواهیم داشت که به ما امکان می‌دهد کم‌ارزش‌ترین بیت $x$ را با مقایسه $y^{2^k}$ با $g$ تعیین کنیم. حال فرض کنید $x=x_0 + 2^k x_1$، که در آن $x_0$ بخش معلوم و $x_1$ بخش نامعلوم است. آنگاه:

$$ g^{x_0+2^k x_1} \equiv y \pmod{2^d}. $$

با ضرب طرفین در $g^{-x_0}$، خواهیم داشت:

$$ g^{2^k x_1} \equiv (g^{-x_0} y) \pmod{2^d}. $$

اکنون، با $d-k-1$ بار به توان دو رساندن طرفین، می‌توانیم بیت بعدی $x$ را به دست آوریم و در نهایت تمام بیت‌های آن را بازیابی کنیم.

مراجع