> The first problem is that when I take SQRT(a), where a is a large
> integer (in this case, 2220223), I just get back SQRT(2220223). Does
> this mean a doesn't have a square root?
This means that it has no square factors. sqrt(15) simplifies to
sqrt(15); sqrt(8) simplifies to 2*sqrt(2). For large numbers, Maxima
does not try to factor fully by default: sqrt(1009^3) =>
sqrt(1027243729); but sqrt(1009^3),intfaclim:5000 => 1009*sqrt(1009).
> The second problem is that what I actually need to do is find
> the square root of a mod n, where n is 20490901. Any tips on
> how to do that would be appreciated.
Maxima can do this for prime moduli using polynomial factorization:
factor(x^2-12),modulus:1009 => (x - 298) (x + 298), though this will be
extremely slow for large moduli. For example,
factor(x^2-7),modulus:300007 takes 10 secs on a 1Ghz machine. There are
fast algorithms for modular root-finding (Google search for sqrtmod --
Mathematica's algorithm is described in
http://documents.wolfram.com/v4/AddOns/StandardPackages/NumberTheory/Num
berTheoryFunctions.html). Perhaps you could implement one of these
algorithms for Maxima and contribute it?
-s