C++로 모듈로 p에서 제곱근 구하기 — Shanks-Tonelli 알고리즘 완벽 가이드

이 문제에서는 두 값 n과 소수 p가 주어지며, 우리의 목표는 모듈로 p(Modulo p) 하에서의 제곱근을 찾는 것입니다.

문제 이해하기

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

입력 : n = 4, p = 11
출력 : 9

위 예제에서 9² = 81이고, 81 mod 11 = 4이므로 9는 모듈로 11에서 4의 제곱근이 됩니다.

해결 접근 방식: Tonelli-Shanks 알고리즘

이 문제는 Tonelli-Shanks 알고리즘을 사용하여 해결할 수 있습니다.

Tonelli-Shanks 알고리즘은 모듈러 산술(modular arithmetic)에서 x² ≡ n (mod p) 형태의 합동(congruence)을 만족하는 값 x를 구하는 데 사용되는 대표적인 알고리즘입니다.

알고리즘 단계

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을 만족하는 값 q를 찾습니다.

4단계 — 반복문을 통해 m > 0인 조건에서 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

C++ 구현 예제

아래 프로그램은 위에서 설명한 솔루션의 동작 방식을 보여줍니다.

#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;
}

// 최대공약수(GCD) 계산 함수
int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

// b의 위수(order)를 구하는 함수
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++;
    }
}

// x를 2의 거듭제곱으로 나누어 s와 e를 구하는 함수
int findx2e(int x, int& e) {
    e = 0;
    while (x % 2 == 0) {
        x /= 2;
        e++;
    }
    return x;
}

// 모듈로 p에서의 제곱근을 계산하는 핵심 함수
int calcSquareRoot(int n, int p) {
    if (gcd(n, p) != 1) {
        return -1;
    }
    // 오일러 기준(Euler's criterion)으로 해 존재 여부 확인
    if (powerMod(n, (p - 1) / 2, p) == (p - 1)) {
        return -1;
    }
    int s, e;
    s = findx2e(p - 1, e);
    // 비이차잉여(non-residue) q 찾기
    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<<"모듈러 제곱근이 존재하지 않습니다.";
    else
        cout<<"해당 수의 모듈러 제곱근은 "<<sqrtVal<<" 입니다.";
}

실행 결과

해당 수의 모듈러 제곱근은 9 입니다.

정리

Tonelli-Shanks 알고리즘은 소수 p에 대한 모듈러 제곱근을 효율적으로 구할 수 있는 강력한 방법입니다. 특히 암호학 분야에서 타원 곡선 연산 등에 널리 활용되며, 오일러 판별법(Euler's criterion)을 통해 해의 존재 여부를 먼저 확인한 뒤, 비이차잉여 원소를 이용해 반복적으로 후보값을 갱신하는 것이 핵심 원리입니다.