Table of Contents
The problem of finding a discrete root is defined as follows. Given a prime $n$ and two integers $a$ and $k$, find all $x$ for which:
$x^k \equiv a \pmod n$
1. The algorithm
We will solve this problem by reducing it to the discrete logarithm problem.
Let’s apply the concept of a primitive root modulo $n$. Let $g$ be a primitive root modulo $n$. Note that since $n$ is prime, it must exist, and it can be found in $O(Ans \cdot \log \phi (n) \cdot \log n) = O(Ans \cdot \log^2 n)$ plus time of factoring $\phi (n)$.
We can easily discard the case where $a = 0$. In this case, obviously there is only one answer: $x = 0$.
Since we know that $n$ is a prime and any number between 1 and $n-1$ can be represented as a power of the primitive root, we can represent the discrete root problem as follows:
$(g^y)^k \equiv a \pmod n$
where
$x \equiv g^y \pmod n$
This, in turn, can be rewritten as
$(g^k)^y \equiv a \pmod n$
Now we have one unknown $y$, which is a discrete logarithm problem. The solution can be found using Shanks’ baby-step giant-step algorithm in $O(\sqrt {n} \log n)$ (or we can verify that there are no solutions).
Having found one solution $y_0$, one of solutions of discrete root problem will be $x_0 = g^{y_0} \pmod n$.
2. Finding all solutions from one known solution
To solve the given problem in full, we need to find all solutions knowing one of them: $x_0 = g^{y_0} \pmod n$.
Let’s recall the fact that a primitive root always has order of $\phi (n)$, i.e. the smallest power of $g$ which gives 1 is $\phi (n)$. Therefore, if we add the term $\phi (n)$ to the exponential, we still get the same value:
$x^k \equiv g^{ y_0 \cdot k + l \cdot \phi (n)} \equiv a \pmod n \forall l \in Z$
Hence, all the solutions are of the form:
$x = g^{y_0 + \frac {l \cdot \phi (n)}{k}} \pmod n \forall l \in Z$.
where $l$ is chosen such that the fraction must be an integer. For this to be true, the numerator has to be divisible by the least common multiple of $\phi (n)$ and $k$. Remember that least common multiple of two numbers $lcm(a, b) = \frac{a \cdot b}{gcd(a, b)}$; we’ll get
$x = g^{y_0 + i \frac {\phi (n)}{gcd(k, \phi (n))}} \pmod n \forall i \in Z$.
This is the final formula for all solutions of the discrete root problem.
3. 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); }