이 문제에서는 두 개의 값 n과 소수 p가 주어집니다. 우리의 임무는 Modulo p에서 Square Root를 찾는 것입니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
Input : n = 4, p = 11 Output : 9
솔루션 접근 방식
여기에서는 Tonelli-Shanks 알고리즘을 사용할 것입니다. .
토넬리-샹크스 알고리즘 모듈식 산술에서 x2 =n(mod p) 형식의 합동으로 값 x를 푸는 데 사용됩니다.
shank의 Tonelli 알고리즘을 사용하여 모듈로 제곱근을 찾는 알고리즘 -
1단계 − $(n^{((p-1)/2)})(mod\:p)$의 값을 구합니다. 값이 p -1이면 모듈러 제곱근이 불가능합니다.
2단계 − 그러면 p - 1 값을 (s * 2 e ). 여기서 s는 홀수이고 양수이고 e는 양수입니다.
3단계 − 값 q^((p-1)/2)(mod p) =-1
을 계산합니다.4단계 - 0보다 큰 m에 대해 루프를 사용하고 x의 값을 업데이트합니다.
b^(2^m) - 1(mod p)이 되도록 m을 찾으십시오. 여기서 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