MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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.