Trong bài toán này, chúng ta được cho hai giá trị n và một số nguyên tố p. Nhiệm vụ của chúng ta là tìm căn bậc hai dưới modulo p (Khi p dạng 4*i + 3). Ở đây, p có dạng (4*i + 3) tức là p % 4 = 3 với i > 1 và p là số nguyên tố.
Một số ví dụ: 7, 11, 19, 23, 31...
Hãy xem ví dụ sau để hiểu bài toán:
Input : n = 3, p = 7 Output :
Phương pháp giải
Một giải pháp đơn giản là dùng vòng lặp. Ta lặp từ 2 đến (p-1). Với mỗi giá trị, kiểm tra xem bình phương có phải căn bậc hai modulo p là n hay không.
Ví dụ
Chương trình minh họa cho giải pháp
#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; }Kết quả
Square root under modulo is 5
Một phương pháp khác là dùng trực tiếp công thức:
Nếu p dạng (4*i + 3) và để căn bậc hai tồn tại, nó sẽ là $+/-n^{(p+1)/4}$
Ví dụ
Chương trình minh họa cho giải pháp
#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; }Kết quả
Square root under modulo is 9