C++에서 Modulo p(p가 4*i + 3의 형태일 때)에서 제곱근 찾기

이 문제에서는 두 개의 값 n과 소수 p가 주어집니다. 우리의 임무는 Modulo p에서 Square Root를 찾는 것입니다(p가 4*i + 3의 형태일 때). 여기서 p는 (4*i + 3) 형식입니다. 즉, i> 1이고 p가 소수인 경우 p % 4 =3입니다.

7, 11, 19, 23, 31...

문제를 이해하기 위해 예를 들어 보겠습니다.

Input : n = 3, p = 7
Output :

해결 방법

문제에 대한 간단한 해결책은 루프를 사용하는 것입니다. 우리는 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