You already bring this idea up when you mention RSA but I want to make the point more generally: There are very good methods for solving polynomial equations modulo primes and prime powers. The only good way to solve an equation modulo $N$ is to factor $N$; solve modulo each prime power dividing $N$, and use Chinese remainder to put a solution back together. This is true even for computing square roots.