इस समस्या में, हमें दो मान 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
