Дискрет язгуур¶
Дискрет язгуур олох бодлого дараах байдлаар тодорхойлогдоно. Анхны тоо $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$ байгаа бөгөөд энэ бол дискрет логарифмын бодлого юм. Шийдийг Шанксын 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$.
Энэ бол дискрет язгуурын бодлогын бүх шийдийн эцсийн томьёо юм.
Implementation¶
Here is a full implementation, including procedures for finding the primitive root, discrete log and finding and printing all solutions.
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);
}