이 문제에서는 소수 N이 하나 주어지며, 우리의 목표는 이 소수에 대한 모듈로 원시근(primitive root)을 구하는 것입니다.
원시근(Primitive Root)이란?
어떤 수의 원시근이란 N보다 작은 수 r 중에서, x가 [0, n-2] 범위 내의 모든 값에 대해 rx (mod N)의 결과가 항상 서로 다른 값을 갖는 수를 의미합니다.
예시를 통해 문제를 살펴보겠습니다.
입력 : N = 5 출력 : 2
N = 5인 경우 원시근은 2와 3으로 총 두 개이며, 그중 가장 작은 원시근은 2입니다. 참고로 소수 N의 원시근 개수는 항상 φ(N-1)과 같습니다.
해결 접근 방법
가장 단순한 해결 방법은 전수 조사(trial) 방식입니다. 2부터 (N-1)까지의 모든 수에 대해 x를 [0, n-2] 범위에서 대입하며 조건을 검사하고, 조건을 만족하는 값을 찾으면 탐색을 종료합니다.
이 방법은 구현이 간단하지만 시간 복잡도가 O(N2) 수준이므로, N이 커질 경우 실행 시간이 크게 늘어나는 단점이 있습니다.
따라서 더 효율적인 해결책은 오일러 피(Euler Totient) 함수 φ(N)를 활용하는 것입니다.
어떤 수 r이 N의 원시근이 되려면, r의 모듈로 N에 대한 곱셈 위수(multiplicative order)가 φ(N)과 같아야 합니다. 이를 확인하는 절차는 다음과 같습니다.
- 소수 N에 대해 (N-1)의 모든 소인수를 구합니다.
- (N-1)을 각 소인수 q로 나눈 지수, 즉 (N-1)/q에 대한 거듭제곱 값을 계산합니다.
- r(N-1)/q mod n의 값이 어떤 소인수 q에 대해서도 1이 되지 않으면 r은 원시근입니다.
- 하나의 수에는 여러 개의 원시근이 존재할 수 있지만, 여기서는 가장 작은 원시근만 필요하므로 처음 발견된 값을 반환합니다.
구현 예제
다음 예제를 통해 문제 해결 과정을 살펴보겠습니다.
#include<bits/stdc++.h>
using namespace std;
int calcPowerMod(int x, unsigned int y, int p){
int modVal = 1;
x = x % p;
while (y > 0){
if (y & 1)
modVal = (modVal*x) % p;
y = y >> 1;
x = (x*x) % p;
}
return modVal;
}
void findAllPrimeFactors(unordered_set<int> &s, int n){
while (n%2 == 0){
s.insert(2);
n = n/2;
}
for (int i = 3; i*i <= n; i = i+2){
while (n%i == 0){
s.insert(i);
n = n/i;
}
}
if (n > 2)
s.insert(n);
}
int findSmallestPrimitiveRoot(int n){
unordered_set<int> primes;
int phi = n-1;
findAllPrimeFactors(primes, phi);
for (int r=2; r<=phi; r++){
bool flag = false;
for (auto it = primes.begin(); it != primes.end(); it++){
if (calcPowerMod(r, phi/(*it), n) == 1){
flag = true;
break;
}
}
if (flag == false)
return r;
}
return -1;
}
int main(){
int n = 809;
cout<<"The smallest primitive root is "<<findSmallestPrimitiveRoot(n);
return 0;
}
실행 결과
The smallest primitive root is 3