C++에서 모듈로 p 하의 제곱근 구하기 — p가 4i+3 형태일 때

문제 개요

이 문제에서는 두 값 n과 소수 p가 주어지며, 모듈로 p(modulo p) 하에서의 제곱근을 찾는 것이 목표입니다. 여기서 p는 반드시 4×i+3 형태여야 합니다. 즉, i > 1일 때 p % 4 = 3을 만족하는 소수라는 뜻입니다.

이 조건을 만족하는 수로는 7, 11, 19, 23, 31 등이 있습니다.

예시를 통해 문제를 살펴보겠습니다.

입력 : n = 3, p = 7
출력 : 제곱근이 존재하지 않음 (3은 7의 이차 잉여가 아님)

방법 1 — 반복문을 이용한 완전 탐색

가장 단순한 해결 방법은 반복문을 사용하는 것입니다. 2부터 (p − 1)까지의 값을 차례대로 검사하면서, 각 값의 제곱을 p로 나눈 나머지가 n과 일치하는지 확인합니다.

구현이 매우 쉽다는 장점이 있지만, 시간 복잡도가 O(p)이므로 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;
}

출력 결과

Square root under modulo is 5

방법 2 — 수학 공식 직접 적용

훨씬 효율적인 방법은 공식을 직접 사용하는 것입니다. p가 4×i+3 형태일 때, 만약 제곱근이 존재한다면 그 값은 다음과 같습니다.

±n^(p+1)/4

이 공식은 페르마의 소정리와 오일러 판정법에서 유도됩니다. p ≡ 3 (mod 4)인 소수에서 n이 이차 잉여(quadratic residue)라면, n^(p+1)/4 mod p가 곧 제곱근이 됩니다. 계산에는 모듈러 거듭제곱(modular exponentiation)을 활용하므로 시간 복잡도는 O(log 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;
}

출력 결과

Square root under modulo is 9

마무리

모듈로 p 하의 제곱근을 구할 때 p가 4i+3 형태라면, 단순 반복 대신 n^(p+1)/4 공식을 활용하는 것이 효율적입니다. 완전 탐색은 O(p)의 시간이 필요한 반면, 공식 기반 접근은 O(log p)만에 결과를 얻을 수 있습니다. 또한 계산된 후보 값을 실제로 제곱해 검증하는 과정을 통해 해당 제곱근이 존재하는지 여부까지 정확하게 판별할 수 있다는 점도 기억할 만합니다.