Solving quadratic or higher degree congruence with very large modulus.

Question

Is there any general way to solve a polynomial congruence with a very large modulus?

An example could be

$$ x^2-377x+1\equiv 0 \pmod {8683317618811886495518194401279999999 } $$

or $$ x^2-29478x\equiv 13^{67} \pmod {17^{2001}} $$

Answer 1

If you can factor the modulus into coprime factors, you can solve the congruence with respect to each factor and then use the Chinese Remainder Theorem. On the other hand, being able to solve $x^2 = a \mod m$ would give you the ability to factor $m$.

EDIT: For lots more on these questions, see "Basic algorithms in number theory" by Joe Buhler and Stan Wagon

Answer 2

Algorithms for this are included in Mathematica. E.g.:

Solve[x^2 - 29478*x == 13^67, x, Modulus -> 17^2001]

yields the two solutions in an eyeblink.