মডুলো p-এ স্কয়ার রুট বের করা (যখন p হল 4*i + 3 রূপে) C++-এ

এই সমস্যায়, আমাদের দুটি মান n এবং একটি প্রাইম নাম্বার p দেওয়া আছে। আমাদের কাজ হল মডুলো p-এ স্কয়ার রুট বের করা (যখন p হল 4*i + 3 রূপে)। এখানে p হল (4*i + 3) রূপে অর্থাৎ p % 4 = 3 i > 1 এর জন্য এবং p একটি প্রাইম নাম্বার।

একই রকম কিছু সংখ্যা: 7, 11, 19, 23, 31...

উদাহরণ

সমস্যাটি বুঝতে একটি উদাহরণ নিই:

ইনপুট : n = 3, p = 7
আউটপুট :

সমাধানের পদ্ধতি

এই সমস্যার একটি সহজ সমাধান হল লুপ ব্যবহার করা। আমরা 2 থেকে (p-1) পর্যন্ত লুপ চালাব। এবং প্রতিটি মানের জন্য চেক করব এর স্কয়ার মডুলো p-তে n কি না।

উদাহরণ প্রোগ্রাম (সহজ লুপ পদ্ধতি)

আমাদের সমাধানের কাজকাণ্ড ব্যাখ্যা করার প্রোগ্রাম:

#include <iostream>
using namespace std;

void findSquareRootMod(int n, int p) {
    n = n % p;
    for (int i = 2; i < p; i++) {
        if ((i * i) % p == n) {
            cout << "Square root under modulo is " << i;
            return;
        }
    }
    cout << "Square root doesn't exist";
}

int main() {
    int p = 11;
    int n = 3;
    findSquareRootMod(n, p);
    return 0;
}

আউটপুট

Square root under modulo is 5

একটি আরো সরল পদ্ধতি হল সরাসরি ফর্মুলা ব্যবহার করা:

যদি p (4*i + 3) রূপের হয় এবং স্কয়ার রুট থাকার জন্য এটি হবে $+/-n^{(p+1)/4}$

উদাহরণ প্রোগ্রাম (ফর্মুলা পদ্ধতি)

আমাদের সমাধানের কাজকাণ্ড ব্যাখ্যা করার প্রোগ্রাম:

#include <iostream>
using namespace std;

int calcPowerVal(int x, int y, int p) {
    int res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % p;
        y /= 2;
        x = (x * x) % p;
    }
    return res;
}

void squareRoot(int n, int p) {
    if (p % 4 != 3) {
        cout << "Invalid Input";
        return;
    }
    n = n % p;
    int sr = calcPowerVal(n, (p + 1) / 4, p);
    if ((sr * sr) % p == n) {
        cout << "Square root under modulo is " << sr;
        return;
    }
    sr = p - sr;
    if ((sr * sr) % p == n) {
        cout << "Square root is " << sr;
        return;
    }
    cout << "Square root doesn't exist ";
}

int main() {
    int p = 11;
    int n = 4;
    squareRoot(n, p);
    return 0;
}

আউটপুট

Square root under modulo is 9