I am trying to put together the techniques involved in solving $$x^e\equiv a\pmod n, \text{ for known } n\in\mathbb N^*, e\in\mathbb N^*, a\in\mathbb Z_n, \text{ unknown }x\in\mathbb Z_n$$
I'm interested in the slightly different problems of
- determining if there are solutions,
- counting the solutions,
- finding the smallest non-negative solution,
- finding all the solutions.
I would greatly appreciate a pointer to a reference text, and (even more) bridging the gaps or otherwise improving the following.
Trivial cases
$n=1$: the single element there is in $\mathbb Z_1$ is solution (we can see this as any $x\in\mathbb Z$).
$e=1$: the single solution modulo $n$ is $x=a\pmod n$.
Possible reduction to prime exponent
If $e$ is composite, and $q$ is a prime dividing $e$, then we have the option to define $y=x^{e/q}\pmod n$, transforming the equation into $y^q\equiv a\pmod n$; solve that; then for each solution $y$ (if any) solve $x^{e/q}\equiv y\pmod n$, which has a smaller exponent than the original.
Ultimately, if we can factor the original exponent, and could solve the problem for any prime exponent, we are done. We can do this reduction at any point, and might not want to use it upfront, for it tends to increase the number of problems to solve.
Reduction to modulus $p^s$ for prime $p$
If $n$ is composite, and $p$ is a prime dividing $n$ with multiplicity $s\in\mathbb N^*$ [that is, $p^s$ divides $n$, but $p$ does not divide $n/p^s$], then we can subdivide the problem into $x^e\equiv a\pmod{p^s}$ and $x^e\equiv a\pmod{n/p^s}$, then recombine the results (if any) using the Chinese Remainder Theorem.
Ultimately, if we can factor the original modulus, we can subdivide the main problem into as many subproblems as there are distinct primes dividing $n$, and the number of overall solutions modulo $n$ will be the product of the number of solutions of each subproblem. We hereafter reduce to $x^e\equiv a\pmod{p^s}$ with $p$ prime.
Gap#1: When we use the above reduction, and there is more than one solution modulo $n$, is there a method to find the the smallest non-negative solution faster than finding all solutions and keeping the smallest?
Solving $x^e\equiv0\pmod{p^s}$
It can happen that $a\equiv0\pmod{p^s}$, and we want to solve $x^e\equiv0\pmod{p^s}$.
The solutions are $x_k=k\cdot p^{\lceil s/e\rceil}\pmod{p^s}, k\in\{0\dots p^{s-\lceil s/e\rceil}-1\}$ [Proof follows from the observation that, when using representation in base $p$ with $p$ square-free (including any prime $p$ and the familiar base $10$), if $x\in\mathbb N^*$ has exactly $z$ zero digits on the right, then $x^e$ has exactly $e\cdot z$ zero digits on the right].
Hereafter we reduce to $x^e\equiv a\pmod{p^s}$ with $p$ prime and $a\not\equiv0\pmod{p^s}$.
Gap#2: Is there some general reduction of the modulus from prime power to prime?
Solving $x^e\equiv a\pmod p,a\not\equiv0\pmod p$
Fermat's little theorem states that $x\not\equiv0\pmod p\implies x^{p-1}\equiv1\pmod p$. This motivates considering the following cases:
- $e\equiv0\pmod{p-1}$ and $a\equiv1\pmod p$:
There are $p-1$ solutions modulo $p$, defined by $x\not\equiv0\pmod p$. - $e\equiv0\pmod{p-1}$ and $a\not\equiv1\pmod p$ [in addition to $a\not\equiv0\pmod p$]:
There is no solution. - $\gcd(e,p-1)=1$ [implying $e\not\equiv0\pmod{p-1}$]:
With $d=e^{-1}\bmod(p-1)$, the single solution modulo $p$ is $x=a^d\pmod p$. - $1<\gcd(e,p-1)<p-1$ [implying $e\not\equiv0\pmod{p-1}$]:
We can reduce $e$ to $e\bmod(p-1)$ without changing the outcome of the equation, then it is a good time to use the already discussed reduction to prime exponent. We are left with the task of solving $x^q\equiv a\pmod p\text{ for }p\text{ and }q\text{ prime},q\text{ dividing }p-1,a\not\equiv0\pmod p$.
Unless I err, this has either no solution or $q$ solutions modulo $p$.
Gap#3: Except perhaps for $q=2$, I have no proof of that last statement; and (except by enumeration) I do not know how to determine if there are solutions (that's the problem of determining degree-$q$ residuosity, or is it residuacity); much less efficiently find solutions; or even the expected cost (time, memory) of these tasks, which I suspect are hard in the general case.
