원시근¶

정의¶

모듈러 연산에서 $n$과 서로소인 모든 수가 $n$을 법으로 하여 $g$의 거듭제곱과 합동이면, 수 $g$를 primitive root modulo n이라고 부릅니다. 수학적으로 $g$가 primitive root modulo n일 필요충분조건은 $\gcd(a, n) = 1$을 만족하는 임의의 정수 $a$에 대해 다음을 만족하는 정수 $k$가 존재하는 것입니다:

$g^k \equiv a \pmod n$.

이때 $k$를 $n$을 법으로 하고 $g$를 밑으로 하는 $a$의 index 또는 discrete logarithm이라고 부릅니다. 또한 $g$를 $n$을 법으로 하는 정수의 곱셈군의 generator라고도 부릅니다.

특히 $n$이 소수인 경우, 원시근의 거듭제곱은 $1$부터 $n-1$까지의 모든 수를 거칩니다.

존재성¶

$n$을 법으로 하는 원시근이 존재할 필요충분조건은 다음과 같습니다:

$n$이 1, 2, 4이거나,
$n$이 홀수 소수의 거듭제곱 $(n = p^k)$이거나,
$n$이 홀수 소수의 거듭제곱의 두 배 $(n = 2 \cdot p^k)$인 경우입니다.

이 정리는 1801년에 Gauss가 증명하였습니다.

오일러 함수와의 관계¶

$g$를 $n$을 법으로 하는 원시근이라고 합시다. 그러면 $g^k \equiv 1 \pmod n$을 만족하는 가장 작은 수 $k$가 $\phi (n)$과 같음을 보일 수 있습니다. 또한 그 역도 성립하며, 이 글에서는 이 사실을 이용하여 원시근을 찾습니다.

나아가 $n$을 법으로 하는 원시근이 존재한다면, 그 개수는 $\phi (\phi (n) )$과 같습니다.

원시근을 찾는 알고리즘¶

단순한 알고리즘은 $[1, n-1]$ 범위의 모든 수를 고려하는 것입니다. 그런 다음 각 수의 모든 거듭제곱을 계산하여 그것들이 모두 서로 다른지 확인함으로써 각 수가 원시근인지 판별합니다. 이 알고리즘의 복잡도는 $O(g \cdot n)$이며, 이는 너무 느립니다. 이 절에서는 잘 알려진 몇 가지 정리를 이용하여 더 빠른 알고리즘을 제시합니다.

이전 절에서 $g^k \equiv 1 \pmod n$을 만족하는 가장 작은 수 $k$가 $\phi (n)$이면 $g$가 원시근임을 알았습니다. $n$과 서로소인 임의의 수 $a$에 대해 오일러 정리로부터 $a ^ { \phi (n) } \equiv 1 \pmod n$임을 알고 있으므로, $g$가 원시근인지 확인하려면 $\phi (n)$보다 작은 모든 $d$에 대해 $g^d \not \equiv 1 \pmod n$임을 확인하는 것으로 충분합니다. 그러나 이 알고리즘은 여전히 너무 느립니다.

라그랑주 정리로부터 $n$을 법으로 하는 임의의 수에 대해 1의 지수는 반드시 $\phi (n)$의 약수여야 함을 알 수 있습니다. 따라서 모든 진약수 $d \mid \phi (n)$에 대해 $g^d \not \equiv 1 \pmod n$임을 확인하는 것으로 충분합니다. 이것만으로도 이미 훨씬 빠른 알고리즘이지만, 더 개선할 수 있습니다.

$\phi (n) = p_1 ^ {a_1} \cdots p_s ^ {a_s}$로 소인수분해합니다. 앞의 알고리즘에서 $\frac { \phi (n) } {p_j}$ 꼴의 $d$ 값만 고려해도 충분하다는 것을 증명하겠습니다. 실제로 $d$를 $\phi (n)$의 임의의 진약수라고 합시다. 그러면 자명하게 $d \mid \frac { \phi (n) } {p_j}$, 즉 $d \cdot k = \frac { \phi (n) } {p_j}$를 만족하는 $j$가 존재합니다. 그런데 $g^d \equiv 1 \pmod n$이라면 다음을 얻게 됩니다.

$g ^ { \frac { \phi (n)} {p_j} } \equiv g ^ {d \cdot k} \equiv (g^d) ^k \equiv 1^k \equiv 1 \pmod n$.

즉, $\frac {\phi (n)} {p_i}$ 꼴의 수 가운데 조건을 만족하지 않는 수가 적어도 하나 존재하게 됩니다.

이제 원시근을 찾는 완전한 알고리즘을 얻었습니다.

먼저 $\phi (n)$을 구하고 이를 소인수분해합니다.
그런 다음 모든 수 $g \in [1, n]$을 순회하면서, 각 수가 원시근인지 확인하기 위해 다음을 수행합니다.
- 모든 $g ^ { \frac {\phi (n)} {p_i}} \pmod n$을 계산합니다.
- 계산한 값이 모두 $1$과 다르면 $g$는 원시근입니다.
이 알고리즘의 실행 시간은 $O(Ans \cdot \log \phi (n) \cdot \log n)$입니다($\phi (n)$의 약수가 $\log \phi (n)$개라고 가정합니다).

Shoup(1990, 1992)은 일반화된 리만 가설을 가정하여 $g$가 $O(\log^6 p)$임을 증명했습니다.

구현¶

다음 코드는 법 p가 소수라고 가정합니다. 임의의 p 값에 대해 동작하게 하려면 $\phi (p)$를 계산하는 부분을 추가해야 합니다.

int powmod (int a, int b, int p) {
    int res = 1;
    while (b)
        if (b & 1)
            res = int (res * 1ll * a % p),  --b;
        else
            a = int (a * 1ll * a % p),  b >>= 1;
    return res;
}

int generator (int p) {
    vector<int> fact;
    int phi = p-1,  n = phi;
    for (int i=2; i*i<=n; ++i)
        if (n % i == 0) {
            fact.push_back (i);
            while (n % i == 0)
                n /= i;
        }
    if (n > 1)
        fact.push_back (n);

    for (int res=2; res<=p; ++res) {
        bool ok = true;
        for (size_t i=0; i<fact.size() && ok; ++i)
            ok &= powmod (res, phi / fact[i], p) != 1;
        if (ok)  return res;
    }
    return -1;
}