I wrote
> William Springer <wmspringer@comcast.net> writes:
>
> > The second problem is that what I actually need to do is find the
> > square root of a mod n, where n is 20490901.
>
> (C1) factor(20490901);
> (D1) 4099 4999
> (C2) p:4099;
> (D2) 4099
>
> Since the modulus is a power of the prime p
I described how to solve x^2 = a mod p^2, sorry for the confusion.
While the actual example a:346 I choose is not suitable for the
problem since it is not a quadratic residue mod the other prime factor
q:4999, you could nevertheless do (C1)-(C6) as previously and then
just
factor(expand(x^2-a)),modulus:q
and back-substitute (which just amounts to one way of solving
simultaneous congruences, of course). And don't forget the other
solutions.
Wolfgang