মন্টগোমেরি গুণন#

সংখ্যাতত্ত্বের অনেক অ্যালগরিদম, যেমন মৌলিকতা টেস্ট বা পূর্ণসংখ্যা উৎপাদক বিশ্লেষণ, এবং ক্রিপ্টোগ্রাফিতে, যেমন RSA, একটি বড় সংখ্যা দিয়ে মডুলো অপারেশন অনেকবার করতে হয়। $x y \bmod{n}$-এর মতো একটি গুণন সাধারণ অ্যালগরিদমে গণনা করা বেশ ধীর, কারণ গুণফল থেকে $n$ কতবার বিয়োগ করতে হবে তা জানতে ভাগের প্রয়োজন। আর ভাগ একটি অত্যন্ত ব্যয়বহুল অপারেশন, বিশেষত বড় সংখ্যার ক্ষেত্রে।

মন্টগোমেরি (মডুলার) গুণন হলো এমন একটি পদ্ধতি যা এই ধরনের গুণন দ্রুততর করে। গুণফল ভাগ করে $n$ একাধিকবার বিয়োগ করার বদলে, এটি নিচের বিটগুলো বাতিল করতে $n$-এর গুণিতক যোগ করে এবং তারপর নিচের বিটগুলো বাদ দেয়।

মন্টগোমেরি রিপ্রেজেন্টেশন#

তবে মন্টগোমেরি গুণন বিনামূল্যে আসে না। অ্যালগরিদমটি কেবল মন্টগোমেরি স্পেসে কাজ করে। এবং গুণ শুরু করার আগে আমাদের সংখ্যাগুলোকে সেই স্পেসে রূপান্তর করতে হবে।

স্পেসের জন্য আমাদের একটি ধনাত্মক পূর্ণসংখ্যা $r \ge n$ প্রয়োজন যা $n$-এর সাথে সহমৌলিক, অর্থাৎ $\gcd(n, r) = 1$। বাস্তবে আমরা সবসময় $r$-কে একটি ধনাত্মক পূর্ণসংখ্যা $m$-এর জন্য $2^m$ নির্বাচন করি, কারণ $r$ দিয়ে গুণ, ভাগ ও মডুলো অপারেশন তখন শিফট ও অন্যান্য বিট অপারেশন ব্যবহার করে দক্ষতার সাথে ইমপ্লিমেন্ট করা যায়। প্রায় সকল প্রয়োগে $n$ একটি বিজোড় সংখ্যা হবে, কারণ জোড় সংখ্যার উৎপাদক বিশ্লেষণ করা কঠিন নয়। তাই $2$-এর প্রতিটি ঘাত $n$-এর সাথে সহমৌলিক হবে।

মন্টগোমেরি স্পেসে একটি সংখ্যা $x$-এর প্রতিনিধি $\bar{x}$ এভাবে সংজ্ঞায়িত:

$$\bar{x} := x \cdot r \bmod n$$

লক্ষ্য করুন, রূপান্তরটি আসলে সেই ধরনের গুণনই যা আমরা অপটিমাইজ করতে চাই। তাই এটি এখনও একটি ব্যয়বহুল অপারেশন। তবে আপনাকে একটি সংখ্যাকে কেবল একবার স্পেসে রূপান্তর করতে হবে। মন্টগোমেরি স্পেসে থাকলে, আপনি দক্ষতার সাথে যত খুশি অপারেশন করতে পারেন। এবং শেষে চূড়ান্ত ফলাফলটিকে আবার রূপান্তর করেন। তাই যতক্ষণ আপনি $n$ মডুলোতে অনেক অপারেশন করছেন, এটি কোনো সমস্যা নয়।

মন্টগোমেরি স্পেসের ভিতরে আপনি এখনও বেশিরভাগ অপারেশন স্বাভাবিকভাবে করতে পারেন। দুটি উপাদান যোগ ($x \cdot r + y \cdot r \equiv (x + y) \cdot r \bmod n$), বিয়োগ, সমতা পরীক্ষা, এমনকি $n$-এর সাথে একটি সংখ্যার গসাগু গণনা করতে পারেন (যেহেতু $\gcd(n, r) = 1$)। সবই স্বাভাবিক অ্যালগরিদমে।

তবে গুণনের ক্ষেত্রে এটি প্রযোজ্য নয়।

আমরা ফলাফল আশা করি:

$$\bar{x} * \bar{y} = \overline{x \cdot y} = (x \cdot y) \cdot r \bmod n.$$

কিন্তু সাধারণ গুণন দেবে:

$$\bar{x} \cdot \bar{y} = (x \cdot y) \cdot r \cdot r \bmod n.$$

তাই মন্টগোমেরি স্পেসে গুণন এভাবে সংজ্ঞায়িত:

$$\bar{x} * \bar{y} := \bar{x} \cdot \bar{y} \cdot r^{-1} \bmod n.$$

মন্টগোমেরি রিডাকশন#

মন্টগোমেরি স্পেসে দুটি সংখ্যার গুণনের জন্য $x \cdot r^{-1} \bmod n$ দক্ষতার সাথে গণনা করা প্রয়োজন। এই অপারেশনকে মন্টগোমেরি রিডাকশন বলা হয়, এবং এটি REDC অ্যালগরিদম হিসেবেও পরিচিত।

যেহেতু $\gcd(n, r) = 1$, আমরা জানি দুটি সংখ্যা $r^{-1}$ ও $n^{\prime}$ আছে যেখানে $0 < r^{-1}, n^{\prime} < n$ এবং

$$r \cdot r^{-1} + n \cdot n^{\prime} = 1.$$

$r^{-1}$ ও $n^{\prime}$ উভয়ই এক্সটেন্ডেড ইউক্লিডিয়ান অ্যালগরিদম ব্যবহার করে গণনা করা যায়।

এই আইডেন্টিটি ব্যবহার করে আমরা $x \cdot r^{-1}$ লিখতে পারি:

$$\begin{aligned} x \cdot r^{-1} &= x \cdot r \cdot r^{-1} / r = x \cdot (-n \cdot n^{\prime} + 1) / r \\ &= (-x \cdot n \cdot n^{\prime} + x) / r \equiv (-x \cdot n \cdot n^{\prime} + l \cdot r \cdot n + x) / r \bmod n\\ &\equiv ((-x \cdot n^{\prime} + l \cdot r) \cdot n + x) / r \bmod n \end{aligned}$$

সমতুল্যতাগুলো যেকোনো ইচ্ছামতো পূর্ণসংখ্যা $l$-এর জন্য ধরে। এর মানে হলো, $x \cdot n^{\prime}$-এর সাথে আমরা $r$-এর যেকোনো গুণিতক যোগ বা বিয়োগ করতে পারি, অন্য কথায়, আমরা $q := x \cdot n^{\prime}$ মডুলো $r$ গণনা করতে পারি।

এটি আমাদের $x \cdot r^{-1} \bmod n$ গণনার নিম্নলিখিত অ্যালগরিদম দেয়:

function reduce(x):
    q = (x mod r) * n' mod r
    a = (x - q * n) / r
    if a < 0:
        a += n
    return a

যেহেতু $x < n \cdot n < r \cdot n$ (এমনকি $x$ গুণনের ফলাফল হলেও) এবং $q \cdot n < r \cdot n$ আমরা জানি $-n < (x - q \cdot n) / r < n$। তাই চূড়ান্ত মডুলো অপারেশনটি একটি মাত্র পরীক্ষা ও একটি যোগ দিয়ে ইমপ্লিমেন্ট করা হয়।

দেখা যাচ্ছে, আমরা কোনো ভারী মডুলো অপারেশন ছাড়াই মন্টগোমেরি রিডাকশন করতে পারি। $r$-কে $2$-এর ঘাত নির্বাচন করলে, অ্যালগরিদমের মডুলো অপারেশন ও ভাগগুলো বিটমাস্কিং ও শিফটিং দিয়ে গণনা করা যায়।

মন্টগোমেরি রিডাকশনের দ্বিতীয় প্রয়োগ হলো একটি সংখ্যাকে মন্টগোমেরি স্পেস থেকে সাধারণ স্পেসে ফিরিয়ে আনা।

ফাস্ট ইনভার্স ট্রিক#

ইনভার্স $n^{\prime} := n^{-1} \bmod r$ দক্ষতার সাথে গণনা করতে, আমরা নিম্নলিখিত ট্রিক ব্যবহার করতে পারি (যা নিউটনের পদ্ধতি থেকে অনুপ্রাণিত):

$$a \cdot x \equiv 1 \bmod 2^k \Longrightarrow a \cdot x \cdot (2 - a \cdot x) \equiv 1 \bmod 2^{2k}$$

এটি সহজেই প্রমাণ করা যায়। যদি $a \cdot x = 1 + m \cdot 2^k$ হয়, তাহলে:

$$\begin{aligned} a \cdot x \cdot (2 - a \cdot x) &= 2 \cdot a \cdot x - (a \cdot x)^2 \\ &= 2 \cdot (1 + m \cdot 2^k) - (1 + m \cdot 2^k)^2 \\ &= 2 + 2 \cdot m \cdot 2^k - 1 - 2 \cdot m \cdot 2^k - m^2 \cdot 2^{2k} \\ &= 1 - m^2 \cdot 2^{2k} \\ &\equiv 1 \bmod 2^{2k}. \end{aligned}$$

এর মানে আমরা $x = 1$ দিয়ে $2^1$ মডুলোতে $a$-এর ইনভার্স হিসেবে শুরু করতে পারি, ট্রিকটি কয়েকবার প্রয়োগ করতে পারি এবং প্রতিটি ইটারেশনে $x$-এর সঠিক বিটের সংখ্যা দ্বিগুণ করতে পারি।

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

GCC কম্পাইলার ব্যবহার করে আমরা $x \cdot y \bmod n$ তখনও দক্ষতার সাথে গণনা করতে পারি যখন তিনটি সংখ্যাই ৬৪ বিট পূর্ণসংখ্যা, কারণ কম্পাইলার __int128 ও __uint128 টাইপ দিয়ে ১২৮ বিট পূর্ণসংখ্যা সমর্থন করে।

long long result = (__int128)x * y % n;

তবে ২৫৬ বিট পূর্ণসংখ্যার জন্য কোনো টাইপ নেই। তাই এখানে আমরা ১২৮ বিট গুণনের একটি ইমপ্লিমেন্টেশন দেখাব।

using u64 = uint64_t;
using u128 = __uint128_t;
using i128 = __int128_t;

struct u256 {
    u128 high, low;

    static u256 mult(u128 x, u128 y) {
        u64 a = x >> 64, b = x;
        u64 c = y >> 64, d = y;
        // (a*2^64 + b) * (c*2^64 + d) =
        // (a*c) * 2^128 + (a*d + b*c)*2^64 + (b*d)
        u128 ac = (u128)a * c;
        u128 ad = (u128)a * d;
        u128 bc = (u128)b * c;
        u128 bd = (u128)b * d;
        u128 carry = (u128)(u64)ad + (u128)(u64)bc + (bd >> 64u);
        u128 high = ac + (ad >> 64u) + (bc >> 64u) + (carry >> 64u);
        u128 low = (ad << 64u) + (bc << 64u) + bd;
        return {high, low};
    }
};

struct Montgomery {
    Montgomery(u128 n) : mod(n), inv(1) {
        for (int i = 0; i < 7; i++)
            inv *= 2 - n * inv;
    }

    u128 init(u128 x) {
        x %= mod;
        for (int i = 0; i < 128; i++) {
            x <<= 1;
            if (x >= mod)
                x -= mod;
        }
        return x;
    }

    u128 reduce(u256 x) {
        u128 q = x.low * inv;
        i128 a = x.high - u256::mult(q, mod).high;
        if (a < 0)
            a += mod;
        return a;
    }

    u128 mult(u128 a, u128 b) {
        return reduce(u256::mult(a, b));
    }

    u128 mod, inv;
};

দ্রুত রূপান্তর#

মন্টগোমেরি স্পেসে একটি সংখ্যা রূপান্তরের বর্তমান পদ্ধতিটি বেশ ধীর। আরো দ্রুত উপায় আছে।

নিম্নলিখিত সম্পর্কটি লক্ষ্য করুন:

$$\bar{x} := x \cdot r \bmod n = x \cdot r^2 / r = x * r^2$$

স্পেসে একটি সংখ্যা রূপান্তর করা হলো সংখ্যাটির সাথে $r^2$-এর মন্টগোমেরি স্পেসের ভিতরে গুণন। তাই আমরা $r^2 \bmod n$ প্রিকম্পিউট করতে পারি এবং ১২৮ বার শিফট করার বদলে একটি গুণন করতে পারি।

নিম্নলিখিত কোডে আমরা r2-কে -n % n দিয়ে ইনিশিয়ালাইজ করি, যা $r - n \equiv r \bmod n$-এর সমতুল্য, এটিকে ৪ বার শিফট করে $r \cdot 2^4 \bmod n$ পাই। এই সংখ্যাটিকে মন্টগোমেরি স্পেসে $2^4$ হিসেবে ব্যাখ্যা করা যায়। এটিকে ৫ বার বর্গ করলে পাই $(2^4)^{2^5} = (2^4)^{32} = 2^{128} = r$ মন্টগোমেরি স্পেসে, যা ঠিক $r^2 \bmod n$।

struct Montgomery {
    Montgomery(u128 n) : mod(n), inv(1), r2(-n % n) {
        for (int i = 0; i < 7; i++)
            inv *= 2 - n * inv;

        for (int i = 0; i < 4; i++) {
            r2 <<= 1;
            if (r2 >= mod)
                r2 -= mod;
        }
        for (int i = 0; i < 5; i++)
            r2 = mul(r2, r2);
    }

    u128 init(u128 x) {
        return mult(x, r2);
    }

    u128 mod, inv, r2;
};