C++로 소수 N의 최소 원시근(Primitive Root) 구하는 방법

문제 설명

이 문제에서는 하나의 소수 N이 주어지며, 우리의 과제는 N modulo N에 대한 원시근(primitive root)을 찾아 출력하는 것입니다.

소수 N의 원시근이란 [1, N-1] 범위에 속하는 정수 x 중에서, k가 [0, N-2] 범위에 있을 때 x^k (mod N)의 값들이 모두 서로 다르게 나타나는 수를 의미합니다. 쉽게 말해, x의 거듭제곱을 N으로 나눈 나머지가 1부터 N-1까지의 모든 값을 빠짐없이 한 번씩 순환하는 수입니다.

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

입력: 13
출력: 2

13의 경우 2가 원시근인데, 그 이유는 2의 거듭제곱을 13으로 나눈 나머지(2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1)가 1부터 12까지의 모든 값을 정확히 한 번씩 포함하기 때문입니다.

접근 방법: 오일러 피 함수(Euler's Totient Function)

이 문제를 해결하려면 오일러 피 함수라는 수학적 개념을 활용해야 합니다.

오일러 피 함수는 1부터 n까지의 수 중에서 n과 서로소인 수의 개수를 세는 함수입니다. 여기서 어떤 수 i가 n과 서로소라는 것은 GCD(i, n) = 1, 즉 두 수의 최대공약수가 1이라는 뜻입니다.

풀이의 핵심 아이디어는 다음과 같습니다. 어떤 수 x의 modulo n에서 곱셈 위수(multiplicative order)가 오일러 피 함수 값과 같다면 x는 원시근이고, 그렇지 않다면 원시근이 아닙니다. 따라서 후보 수마다 이 조건을 검사하면 됩니다.

참고: 소수 n의 오일러 피 함수 값은 항상 n-1입니다.

알고리즘 동작 원리

효율적인 검사를 위해 먼저 n-1을 소인수분해하여 소인수들의 집합을 구합니다. 그다음 각 후보 r(2부터 n-1까지)에 대해 모든 소인수 q에 대하여 r^(n-1)/q mod n ≠ 1인지 확인합니다. 모든 소인수에 대해 이 조건을 만족한다면 r은 원시근입니다.

C++ 구현 코드

#include<bits/stdc++.h>
using namespace std;

// 소수 판별 함수
bool isPrimeNumber(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}

// 모듈러 거듭제곱 계산 (x^y mod p)
int power(int x, unsigned int y, int p) {
    int res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

// n의 소인수 집합 생성
void GeneratePrimes(unordered_set<int> &s, int n) {
    while (n % 2 == 0) {
        s.insert(2);
        n = n / 2;
    }
    for (int i = 3; i <= sqrt(n); i = i + 2) {
        while (n % i == 0) {
            s.insert(i);
            n = n / i;
        }
    }
    if (n > 2)
        s.insert(n);
}

// 가장 작은 원시근 찾기
int findPrimitiveRoot(int n) {
    unordered_set<int> s;
    if (isPrimeNumber(n) == false)
        return -1;
    int ETF = n - 1;
    GeneratePrimes(s, ETF);
    for (int r = 2; r <= ETF; r++) {
        bool flag = false;
        for (auto it = s.begin(); it != s.end(); it++) {
            if (power(r, ETF / (*it), n) == 1) {
                flag = true;
                break;
            }
        }
        if (flag == false)
            return r;
    }
    return -1;
}

int main() {
    int n = 13;
    cout << n << "의 가장 작은 원시근은 " << findPrimitiveRoot(n);
    return 0;
}

실행 결과

13의 가장 작은 원시근은 2

이 알고리즘은 후보 수를 하나씩 검사하는 방식으로 동작하며, 일반적으로 O(N × log N) 수준의 시간 복잡도로 실행됩니다. 원시근은 암호학의 디피-헬만 키 교환(Diffie-Hellman key exchange) 등 다양한 분야에서 활용되는 중요한 개념이므로, 그 판별 방법을 잘 이해해 두는 것이 좋습니다.