এই সমস্যায়, আমাদের দুটি মান n এবং একটি প্রাইম নাম্বার p দেওয়া আছে। আমাদের কাজ হল মডুলো p-এ স্কয়ার রুট বের করা।
উদাহরণ
সমস্যাটি বুঝতে একটি উদাহরণ নিই:
ইনপুট : n = 4, p = 11 আউটপুট : 9
সমাধানের পদ্ধতি
এখানে আমরা টনেলি-শ্যাঙ্কস অ্যালগরিদম ব্যবহার করব।
টনেলি-শ্যাঙ্কস অ্যালগরিদম মডুলার অ্যারিথমেটিক্লে x^2 = n (mod p) রূপের কনগ্রুয়েন্সে x-এর মান বের করতে ব্যবহৃত হয়।
শ্যাঙ্কস টনেলি অ্যালগরিদম দিয়ে মডুলো স্কয়ার রুট বের করার পদ্ধতি:
স্টেপ ১ − $(n^{((p-1)/2)})(mod\:p)$ এর মান বের করুন, যদি এর মান p-1 হয়, তবে মডুলার স্কয়ার রুট সম্ভব নয়।
স্টেপ ২ − তারপর, p-1 কে (s * 2^e) রূপে লিখুন। যেখানে s বিজোড় এবং পজিটিভ, এবং e পজিটিভ।
স্টেপ ৩ − q^((p-1)/2)(mod p) = -1 এর মান ক্যালকুলেট করুন।
স্টেপ ৪ − m > 0 হলে লুপ চালিয়ে x-এর মান আপডেট করুন:
একটি m খুঁজুন যাতে b^(2^m) = 1 (mod p) যেখানে 0 <= m <= r-1।
যদি M = 0 হয়, x রিটার্ন করুন, অন্যথায় মানগুলো আপডেট করুন:
x = x * (g^(2 ^ (r - m - 1)) b = b * (g^(2 ^ (r - m)) g = (g^(2 ^ (r - m - 1)) r = m
উদাহরণ প্রোগ্রাম
আমাদের সমাধানের কাজকাণ্ড ব্যাখ্যা করার প্রোগ্রাম:
#include <iostream>
#include <math.h>
using namespace std;
int powerMod(int base, int exponent, int modulus) {
int result = 1;
base = base % modulus;
while (exponent > 0) {
if (exponent % 2 == 1)
result = (result * base) % modulus;
exponent = exponent >> 1;
base = (base * base) % modulus;
}
return result;
}
int gcd(int a, int b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}
int orderValues(int p, int b) {
if (gcd(p, b) != 1) {
return -1;
}
int k = 3;
while (1) {
if (powerMod(b, k, p) == 1)
return k;
k++;
}
}
int findx2e(int x, int& e) {
e = 0;
while (x % 2 == 0) {
x /= 2;
e++;
}
return x;
}
int calcSquareRoot(int n, int p) {
if (gcd(n, p) != 1) {
return -1;
}
if (powerMod(n, (p - 1) / 2, p) == (p - 1)) {
return -1;
}
int s, e;
s = findx2e(p - 1, e);
int q;
for (q = 2; ; q++) {
if (powerMod(q, (p - 1) / 2, p) == (p - 1))
break;
}
int x = powerMod(n, (s + 1) / 2, p);
int b = powerMod(n, s, p);
int g = powerMod(q, s, p);
int r = e;
while (1) {
int m;
for (m = 0; m < r; m++) {
if (orderValues(p, b) == -1)
return -1;
if (orderValues(p, b) == pow(2, m))
break;
}
if (m == 0)
return x;
x = (x * powerMod(g, pow(2, r - m - 1), p)) % p;
g = powerMod(g, pow(2, r - m), p);
b = (b * g) % p;
if (b == 1)
return x;
r = m;
}
}
int main() {
int n = 3;
int p = 13;
int sqrtVal = calcSquareRoot(n, p);
if (sqrtVal == -1)
cout << "Modular square root is not exist";
else
cout << "Modular square root of the number is " << sqrtVal;
}
আউটপুট
Modular square root of the number is 9
