গার্নারের অ্যালগরিদম#

চাইনিজ রিমেইন্ডার থিওরেম-এর একটি ফলাফল হলো, আমরা বড় সংখ্যাগুলোকে ছোট পূর্ণসংখ্যার একটি অ্যারে ব্যবহার করে উপস্থাপন করতে পারি। উদাহরণস্বরূপ, মনে করি $p$ হলো প্রথম $1000$টি মৌলিক সংখ্যার গুণফল। $p$-তে প্রায় $3000$টি অঙ্ক আছে।

$p$-এর চেয়ে ছোট যেকোনো সংখ্যা $a$-কে একটি অ্যারে $a_1, \ldots, a_k$ আকারে উপস্থাপন করা যায়, যেখানে $a_i \equiv a \pmod{p_i}$। তবে এটি করতে হলে আমাদের স্পষ্টতই জানতে হবে কিভাবে সংখ্যা $a$-কে তার উপস্থাপনা থেকে ফিরে পাওয়া যায়। একটি পদ্ধতি চাইনিজ রিমেইন্ডার থিওরেম সম্পর্কিত নিবন্ধে আলোচনা করা হয়েছে।

এই নিবন্ধে আমরা একটি বিকল্প পদ্ধতি আলোচনা করব, গার্নারের অ্যালগরিদম, যা এই কাজের জন্যও ব্যবহার করা যায়।

মিক্সড র‍্যাডিক্স রিপ্রেজেন্টেশন#

আমরা সংখ্যা $a$-কে মিক্সড র‍্যাডিক্স উপস্থাপনায় প্রকাশ করতে পারি:

$$a = x_1 + x_2 p_1 + x_3 p_1 p_2 + \ldots + x_k p_1 \cdots p_{k-1} \text{ with }x_i \in [0, p_i)$$

মিক্সড র‍্যাডিক্স রিপ্রেজেন্টেশন হলো একটি পজিশনাল সংখ্যা পদ্ধতি, যা সাধারণ সংখ্যা পদ্ধতিগুলোর একটি সাধারণীকরণ, যেমন বাইনারি সংখ্যা পদ্ধতি বা দশমিক সংখ্যা পদ্ধতি। উদাহরণস্বরূপ, দশমিক সংখ্যা পদ্ধতি হলো ১০ ভিত্তি (বা র‍্যাডিক্স) বিশিষ্ট একটি পজিশনাল সংখ্যা পদ্ধতি। প্রতিটি সংখ্যা $0$ থেকে $9$-এর মধ্যে অঙ্কের একটি স্ট্রিং $d_1 d_2 d_3 \dots d_n$ আকারে প্রকাশ করা হয়। উদাহরণস্বরূপ, স্ট্রিং $415$ সংখ্যা $4 \cdot 10^2 + 1 \cdot 10^1 + 5 \cdot 10^0$-কে নির্দেশ করে। সাধারণভাবে, $b$ ভিত্তির পজিশনাল সংখ্যা পদ্ধতিতে অঙ্কের স্ট্রিং $d_1 d_2 d_3 \dots d_n$ সংখ্যা $d_1 b^{n-1} + d_2 b^{n-2} + \cdots + d_n b^0$-কে নির্দেশ করে।

মিক্সড র‍্যাডিক্স পদ্ধতিতে, আমাদের আর একটি মাত্র র‍্যাডিক্স থাকে না। ভিত্তি অবস্থান থেকে অবস্থানে পরিবর্তিত হয়।

গার্নারের অ্যালগরিদম#

গার্নারের অ্যালগরিদম অঙ্কগুলো $x_1, \ldots, x_k$ গণনা করে। লক্ষ্য করুন, অঙ্কগুলো তুলনামূলকভাবে ছোট। অঙ্ক $x_i$ হলো $0$ এবং $p_i - 1$-এর মধ্যে একটি পূর্ণসংখ্যা।

$r_{ij}$ দ্বারা $p_j$ মডুলোতে $p_i$-এর ইনভার্স বোঝানো হোক

$$r_{ij} = (p_i)^{-1} \pmod{p_j}$$

যা মডুলার ইনভার্স-এ বর্ণিত অ্যালগরিদম ব্যবহার করে বের করা যায়।

মিক্সড র‍্যাডিক্স রিপ্রেজেন্টেশন থেকে $a$-কে প্রথম সর্বসমতা সমীকরণে প্রতিস্থাপন করলে আমরা পাই

$$a_1 \equiv x_1 \pmod{p_1}.$$

দ্বিতীয় সমীকরণে প্রতিস্থাপন করলে পাওয়া যায়

$$a_2 \equiv x_1 + x_2 p_1 \pmod{p_2},$$

যেটিকে $x_1$ বিয়োগ করে এবং $p_1$ দিয়ে ভাগ করে পুনর্লিখন করা যায়

$$\begin{array}{rclr} a_2 - x_1 &\equiv& x_2 p_1 &\pmod{p_2} \\ (a_2 - x_1) r_{12} &\equiv& x_2 &\pmod{p_2} \\ x_2 &\equiv& (a_2 - x_1) r_{12} &\pmod{p_2} \end{array}$$

একইভাবে আমরা পাই

$$x_3 \equiv ((a_3 - x_1) r_{13} - x_2) r_{23} \pmod{p_3}.$$

এখন আমরা স্পষ্টভাবে একটি প্যাটার্ন দেখতে পাচ্ছি, যা নিম্নলিখিত কোডে প্রকাশ করা যায়:

for (int i = 0; i < k; ++i) {
    x[i] = a[i];
    for (int j = 0; j < i; ++j) {
        x[i] = r[j][i] * (x[i] - x[j]);

        x[i] = x[i] % p[i];
        if (x[i] < 0)
            x[i] += p[i];
    }
}

তাহলে আমরা শিখলাম কিভাবে $O(k^2)$ সময়ে অঙ্ক $x_i$ গণনা করা যায়। সংখ্যা $a$ এখন পূর্বে উল্লিখিত সূত্র ব্যবহার করে গণনা করা যায়

$$a = x_1 + x_2 \cdot p_1 + x_3 \cdot p_1 \cdot p_2 + \ldots + x_k \cdot p_1 \cdots p_{k-1}$$

উল্লেখযোগ্য যে, বাস্তবে আমাদের প্রায় নিশ্চিতভাবেই আরবিট্রারি-প্রিসিশন অ্যারিথমেটিক ব্যবহার করে উত্তর $a$ গণনা করতে হবে, তবে অঙ্কগুলো $x_i$ (যেহেতু এগুলো ছোট) সাধারণত বিল্ট-ইন টাইপ ব্যবহার করে গণনা করা যায়, এবং তাই গার্নারের অ্যালগরিদম অত্যন্ত দক্ষ।

গার্নারের অ্যালগরিদমের ইমপ্লিমেন্টেশন#

Java ব্যবহার করে এই অ্যালগরিদম ইমপ্লিমেন্ট করা সুবিধাজনক, কারণ এতে BigInteger ক্লাসের মাধ্যমে বড় সংখ্যার বিল্ট-ইন সাপোর্ট আছে।

এখানে আমরা এমন একটি ইমপ্লিমেন্টেশন দেখাচ্ছি যা বড় সংখ্যাগুলোকে সর্বসমতা সমীকরণের একটি সেট আকারে সংরক্ষণ করতে পারে। এটি যোগ, বিয়োগ এবং গুণ সমর্থন করে। এবং গার্নারের অ্যালগরিদম দিয়ে আমরা সমীকরণের সেটটিকে অনন্য পূর্ণসংখ্যায় রূপান্তর করতে পারি। এই কোডে, আমরা $10^9$-এর চেয়ে বড় ১০০টি মৌলিক সংখ্যা নিই, যা $10^{900}$-এর মতো বড় সংখ্যা উপস্থাপন করতে দেয়।

final int SZ = 100;
int pr[] = new int[SZ];
int r[][] = new int[SZ][SZ];

void init() {
    for (int x = 1000 * 1000 * 1000, i = 0; i < SZ; ++x)
        if (BigInteger.valueOf(x).isProbablePrime(100))
            pr[i++] = x;

    for (int i = 0; i < SZ; ++i)
        for (int j = i + 1; j < SZ; ++j)
            r[i][j] =
                BigInteger.valueOf(pr[i]).modInverse(BigInteger.valueOf(pr[j])).intValue();
}

class Number {
    int a[] = new int[SZ];

    public Number() {
    }

    public Number(int n) {
        for (int i = 0; i < SZ; ++i)
            a[i] = n % pr[i];
    }

    public Number(BigInteger n) {
        for (int i = 0; i < SZ; ++i)
            a[i] = n.mod(BigInteger.valueOf(pr[i])).intValue();
    }

    public Number add(Number n) {
        Number result = new Number();
        for (int i = 0; i < SZ; ++i)
            result.a[i] = (a[i] + n.a[i]) % pr[i];
        return result;
    }

    public Number subtract(Number n) {
        Number result = new Number();
        for (int i = 0; i < SZ; ++i)
            result.a[i] = (a[i] - n.a[i] + pr[i]) % pr[i];
        return result;
    }

    public Number multiply(Number n) {
        Number result = new Number();
        for (int i = 0; i < SZ; ++i)
            result.a[i] = (int)((a[i] * 1l * n.a[i]) % pr[i]);
        return result;
    }

    public BigInteger bigIntegerValue(boolean can_be_negative) {
        BigInteger result = BigInteger.ZERO, mult = BigInteger.ONE;
        int x[] = new int[SZ];
        for (int i = 0; i < SZ; ++i) {
            x[i] = a[i];
            for (int j = 0; j < i; ++j) {
                long cur = (x[i] - x[j]) * 1l * r[j][i];
                x[i] = (int)((cur % pr[i] + pr[i]) % pr[i]);
            }
            result = result.add(mult.multiply(BigInteger.valueOf(x[i])));
            mult = mult.multiply(BigInteger.valueOf(pr[i]));
        }

        if (can_be_negative)
            if (result.compareTo(mult.shiftRight(1)) >= 0)
                result = result.subtract(mult);

        return result;
    }
}