이산 근¶
이산 근을 구하는 문제는 다음과 같이 정의됩니다. 소수 $n$과 두 정수 $a$, $k$가 주어질 때, 다음을 만족하는 모든 $x$를 구하십시오:
$x^k \equiv a \pmod n$
알고리즘¶
이 문제는 이산 로그 문제로 환원하여 풉니다.
$n$을 법으로 하는 원시근의 개념을 적용해 봅시다. $g$를 $n$을 법으로 하는 원시근이라고 합시다. $n$이 소수이므로 원시근은 반드시 존재하며, $\phi (n)$을 소인수분해하는 시간에 더해 $O(Ans \cdot \log \phi (n) \cdot \log n) = O(Ans \cdot \log^2 n)$에 찾을 수 있다는 점에 유의하십시오.
$a = 0$인 경우는 쉽게 제외할 수 있습니다. 이 경우 답은 명백히 $x = 0$ 하나뿐입니다.
$n$이 소수이고 1부터 $n-1$ 사이의 모든 수를 원시근의 거듭제곱으로 나타낼 수 있다는 것을 알고 있으므로, 이산 근 문제를 다음과 같이 나타낼 수 있습니다:
$(g^y)^k \equiv a \pmod n$
여기서
$x \equiv g^y \pmod n$
이는 다시 다음과 같이 쓸 수 있습니다.
$(g^k)^y \equiv a \pmod n$
이제 미지수는 $y$ 하나이며, 이는 이산 로그 문제입니다. 해는 Shanks의 baby-step giant-step 알고리즘을 사용하여 $O(\sqrt {n} \log n)$에 구할 수 있습니다(또는 해가 없음을 확인할 수 있습니다).
해 $y_0$ 하나를 찾으면, 이산 근 문제의 해 중 하나는 $x_0 = g^{y_0} \pmod n$이 됩니다.
알려진 해 하나로부터 모든 해 구하기¶
주어진 문제를 완전히 풀려면, 해 중 하나인 $x_0 = g^{y_0} \pmod n$을 알고 있을 때 모든 해를 구해야 합니다.
원시근의 위수는 항상 $\phi (n)$이라는 사실, 즉 1이 되는 $g$의 가장 작은 거듭제곱 지수가 $\phi (n)$이라는 사실을 떠올려 봅시다. 따라서 지수에 $\phi (n)$ 항을 더해도 여전히 같은 값을 얻습니다:
$x^k \equiv g^{ y_0 \cdot k + l \cdot \phi (n)} \equiv a \pmod n \forall l \in Z$
그러므로 모든 해는 다음과 같은 형태입니다:
$x = g^{y_0 + \frac {l \cdot \phi (n)}{k}} \pmod n \forall l \in Z$.
여기서 $l$은 분수가 정수가 되도록 선택합니다. 이것이 성립하려면 분자가 $\phi (n)$과 $k$의 최소공배수로 나누어떨어져야 합니다. 두 수의 최소공배수가 $lcm(a, b) = \frac{a \cdot b}{gcd(a, b)}$임을 기억하면, 다음을 얻습니다.
$x = g^{y_0 + i \frac {\phi (n)}{gcd(k, \phi (n))}} \pmod n \forall i \in Z$.
이것이 이산 근 문제의 모든 해에 대한 최종 공식입니다.
구현¶
다음은 원시근을 찾는 절차, 이산 로그, 그리고 모든 해를 찾아 출력하는 절차를 포함한 전체 구현입니다.
int gcd(int a, int b) {
return a ? gcd(b % a, a) : b;
}
int powmod(int a, int b, int p) {
int res = 1;
while (b > 0) {
if (b & 1) {
res = res * a % p;
}
a = a * a % p;
b >>= 1;
}
return res;
}
// Finds the primitive root modulo p
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 (int factor : fact) {
if (powmod(res, phi / factor, p) == 1) {
ok = false;
break;
}
}
if (ok) return res;
}
return -1;
}
// This program finds all numbers x such that x^k = a (mod n)
int main() {
int n, k, a;
scanf("%d %d %d", &n, &k, &a);
if (a == 0) {
puts("1\n0");
return 0;
}
int g = generator(n);
// Baby-step giant-step discrete logarithm algorithm
int sq = (int) sqrt (n + .0) + 1;
vector<pair<int, int>> dec(sq);
for (int i = 1; i <= sq; ++i)
dec[i-1] = {powmod(g, i * sq * k % (n - 1), n), i};
sort(dec.begin(), dec.end());
int any_ans = -1;
for (int i = 0; i < sq; ++i) {
int my = powmod(g, i * k % (n - 1), n) * a % n;
auto it = lower_bound(dec.begin(), dec.end(), make_pair(my, 0));
if (it != dec.end() && it->first == my) {
any_ans = it->second * sq - i;
break;
}
}
if (any_ans == -1) {
puts("0");
return 0;
}
// Print all possible answers
int delta = (n-1) / gcd(k, n-1);
vector<int> ans;
for (int cur = any_ans % delta; cur < n-1; cur += delta)
ans.push_back(powmod(g, cur, n));
sort(ans.begin(), ans.end());
printf("%d\n", ans.size());
for (int answer : ans)
printf("%d ", answer);
}