इस समस्या में, हमें दो मान n और एक अभाज्य संख्या p दिए गए हैं। हमारा कार्य मॉड्यूलो p के तहत वर्गमूल ज्ञात करना है।
उदाहरण से समझते हैं:
इनपुट: n = 4, p = 11 आउटपुट: 9
समाधान दृष्टिकोण
यहां, हम टोनेली-शैंक्स एल्गोरिथम का उपयोग करेंगे।
टोनेली-शैंक्स एल्गोरिथम मॉड्यूलर अंकगणित में x के मान के लिए x² = n (mod p) रूप के सर्वांगसमता को हल करने के लिए उपयोग किया जाता है।
शैंक्स के टोनेली एल्गोरिथम का उपयोग करके मॉड्यूलो वर्गमूल ज्ञात करने का एल्गोरिथम:
चरण 1 - $(n^{((p-1)/2)})(mod\:p)$ का मान ज्ञात करें, यदि इसका मान p - 1 है, तो मॉड्यूलर वर्गमूल संभव नहीं है।
चरण 2 - फिर, हम मान p - 1 को (s * 2e) के रूप में उपयोग करेंगे। जहां s विषम और धनात्मक है और e धनात्मक है।
चरण 3 - q^((p-1)/2)(mod p) = -1 का मान गणना करें।
चरण 4 - 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
