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 (and p is not 2), we can
check if the quadratic equation has a solution mod p and, if such a
solution (with multiplicity 1) exists, then (Hensel-)lift it to a
solution mod an arbitrary power of p (that is, we can calculate a
p-adic solution)
Take a random example; you could check that it is a quadratic residue
by doing jacobi(a,p).
(C3) a:346;
(D3) 346
Solve the equation mod p
(C4) factor(x^2-a),modulus:p;
(D4) (x - 1081) (x + 1081)
(C5) b:1081;
(D5) 1081
So x is of the form plus or minus
(C6) x:b+y*p;
(D6) 4099 y + 1081
And the original congruence becomes
(C7) solve((a-b^2)/p=2*b*y,y),modulus:p;
(D7) [y = 544]
So the solutions are plus or minus
(C8) x,%;
(D8) 2230937
Check it
(C9) (%^2-a)/p^2;
(D9) 296223
Wolfgang