How does on solve for $x$ in
$x^k \equiv b \pmod n$
where $n$ is not prime and $\gcd(k,\phi(n)) > 1$
Can this be done using Euler's theorem and totient function?
How does on solve for $x$ in
$x^k \equiv b \pmod n$
where $n$ is not prime and $\gcd(k,\phi(n)) > 1$
Can this be done using Euler's theorem and totient function?
The answer is probably no. Even for the simpler congruence
$ x^2 \equiv b \pmod{p} $ with $p$ prime I don't know of any direct way to solve it except in exceptional cases (Though there are fast probabilistic algorithms to find it as Tonnelli and Shank's and also Schoof's algorithm which works in deterministic polynomial time algorithm). To solve your congruence I would do as follows:
I assume that $\gcd(b,n)=1$. Let $d = \gcd(k,n)$, and find $u,v$ such that $uk + v\phi(n) = d$. powering the congruence to the $u$-th power we get the congruence $ x^d \equiv b^u \pmod{n} $ now if $b^{u\phi(n)/d} \not \equiv 1 \pmod{n}$ then you know that there is no solution (because the left hand side is $\equiv 1 \pmod{n}$.
If $b^{u\phi(n)/d} \equiv 1 \pmod{n}$ then you are not sure if there are solutions or not. To check it you should factor $n$ as a product of prime powers, $n = \prod p^t$.
Now, there are solutions to the orignial congruence if and only if for every prime power factor $p^t$ of $n$, we have b^{u \phi(p^t)/d'} \equiv 1 \pmod{ p^t} \quad \text{with } d' = \gcd(d,\phi(p^t)) if any of this congruence fails then there are no solutions.
The problem is reduced to find solutions to each congruence $ x^d \equiv b^u \pmod{p^t} $ and then combine them using the Chinese reminder theorem.
Using the same argument that above we can reduce this to the congruence x^{d'} \equiv b' \pmod{p^t} \quad\text{ for certain }b'\text{ with }\quad b^{\phi(p^t)/d'} \equiv 1 \pmod{p^t}
In the affirmative case then the congruence x^{d'} \equiv b' \pmod{p^t} has exactly d' solutions, that is the polynomial P(x) = x^{d'} - b' is the product of d' linear factors, I don't know of any algorithm that factors modulo $p^t$ in guaranteed polynomial time but there are fast probabilistic ways ways to solve it, for example you can compute polynomial $\gcd$'s using several random values $a$ not divisible by $p$: \gcd( (x+a)^{\phi(p^t)/d'}-1, P(x) ) and using the results to descompose recursively the polynomial $P(x)$ in smaller ones until you get the linear factors.