ফ্যাক্টরাইজেশনের মাধ্যমে বাইনারি এক্সপোনেনশিয়েশন#

$ax^y \pmod{2^d}$ গণনার একটি সমস্যা বিবেচনা করুন, যেখানে পূর্ণসংখ্যা $a$, $x$, $y$ এবং $d \geq 3$ দেওয়া আছে, এবং $x$ বিজোড়।

নিচের অ্যালগরিদমটি $O(d)$ যোগ এবং বাইনারি অপারেশন এবং $y$ দ্বারা একটি একক গুণের মাধ্যমে এই সমস্যা সমাধান করতে দেয়।

$2^d$ মডুলোতে গুণনমূলক গ্রুপের গঠনের কারণে, $x \equiv 1 \pmod 4$ হলে যেকোনো সংখ্যা $x$ কে এভাবে উপস্থাপন করা যায়

$$ 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}$-এর পরিবর্তে $2^d$ মডুলোতে নেওয়া হবে।

এই আর্টিকেলে, আমরা $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) {
        /* divider is considered negative */
        base = -base;
        /* check if result should be negative */
        if (exp & 1) {
            rem = -rem;
        }
    }
    return (mbin_exp_32(rem, mbin_log_32(0, base) * exp));
}

x থেকে 4L(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}}. $$

তাই, আমরা যদি সকল $1 < k < d$-এর জন্য $t_k = 4L(2^n+1)$ প্রিকম্পিউট করি, আমরা যেকোনো সংখ্যা $x$-এর জন্য $4L(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$ দিয়ে গুণ করব যতক্ষণ না এটি $2^d$ মডুলোতে $1$-এ পরিণত হয়। এইভাবে, আমরা $x^{-1}$-এর রিপ্রেজেন্টেশন পাব, অর্থাৎ

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

এটি করতে, আমরা $1 < n < d$ এমন $n$-এর উপর ইটারেট করি। বর্তমান $x$-এর $n$-তম বিট সেট থাকলে, আমরা $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$-এর সমান।

4L(x) থেকে 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}}. $$

এই ফলাফলটি $a=2^n+1$ এবং $b=d-k$-এ প্রয়োগ করলে আমরা অনুমান করি যে $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$-এর সর্বোচ্চ ঘাত, তাই আমাদের প্রয়োজন

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

সুতরাং $v$ অবশ্যই $k-2$-এর চেয়ে বড় বা সমান হতে হবে। এটি একটু অগোছালো এবং এটি প্রশমিত করতে আমরা শুরুতে বলেছিলাম যে আমরা $L(x)$-কে $4$ দ্বারা গুণ করি। এখন যদি আমরা $4L(x)$ জানি, আমরা $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}$ এবং $2k \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;
}

লগারিদম টেবিল গণনা#

লগ-টেবিল গণনা করতে, মডুলো $2$-এর ঘাত হলে পহলিগ-হেলম্যান অ্যালগরিদম পরিবর্তন করা যেতে পারে।

আমাদের মূল কাজ হলো $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$ থাকবে যা $y^{2^k}$-কে $g$-এর সাথে তুলনা করে $x$-এর ক্ষুদ্রতম বিট নির্ধারণ করতে দেয়। এখন ধরুন $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$-এর পরবর্তী বিট পেতে পারি, অবশেষে এর সকল বিট উদ্ধার করতে পারি।

রেফারেন্স#

M30, Hans Petter Selasky, 2009