How to compute modular square roots when modulus is non-prime I am trying to implement James McKee's speed-up of Fermat's factoring algorithm described at http://www.ams.org/journals/mcom/1999-68-228/S0025-5718-99-01133-3/home.html. The algorithm factors semi-primes in time O(n^{1/4}) as follows:
Find the factors of composite N that has no factors less than
2N^{1/4} (use trial division to assure this is so). Define
b=ceil(sqrt(N)) and Q(x,y)=(x+by)^2-Ny^2.

1. Compute modular square root. Choose a prime p greater than
2N^{1/4} and compute the solutions to Q(x,1)==0 (mod p^2). There
are at most two solutions which we denote x_0 and x_1.

2. Find square. For x_i in [x_0,x_1]: Set x=x_i and y=1. While
Q(x,y) is not a square, set r=ceil(p^2/x), x=xr-p^2 and y=r. Abort
the loop, go back to Step 1 and choose a different prime when y
exceeds a given threshold y_{max} in the order of N^{1/4}.

If Q(x,y) is a square, compute gcd(x+by-sqrt(Q(x,y)), N). If the
gcd is between 1 and N it is a non-trivial (not necessarily prime)
factor of N; return it and quit. Otherwise, go back to Step 1 and
choose a different prime. Abort the algorithm when p reaches a
given bound.

I am having trouble with the step "compute the solutions to Q(x,1)==0 (mod p^2)." I need to find the square root of N modulo p^2, but the Tonelli-Shanks algorithm requires the modulus to be an odd prime, so it fails.
I know it is possible to make that calculation. When trying to factor 13290059=3119*4261, I calculate N^{1/4}=60, the smallest prime greater than 2N^{1/4}=127, and the square roots of 13290059 mod 127^2 are 2020 and 14109, which I found at Wolfram|Alpha using PowModList[13290059,1/2,16129].
Is there any way to find the modular square root with a non-prime modulus short of trying every integer from 0 to p^2-1?
 A: Working out the example from your comment. Here $p=127$, and you want to compute modular square roots of $a=13290059$. First we notice that $a\equiv 17 \pmod p$ and $a\equiv 15892 \pmod {p^2}$. You have apparently found that $12^2\equiv 17 \pmod p$, so the two square roots will be congruent to $\pm12\pmod p$. I do the plus sign here.
We are looking for an integer $b$ such that $b^2\equiv 15892 \pmod{127^2}$ and $b\equiv 12 \pmod {127}$. The latter congruence tells us that $b=12+127 m$ for some integer $m$. Then
$$
b^2=12^2+24\cdot 127 m+127^2m^2\equiv 144+24\cdot127 m\pmod{127^2}.
$$
Here $15892-144=15748=127\cdot124$, so the first congruence simplifies first to
$$144+24\cdot127 m\equiv 15892\pmod{127^2}\Leftrightarrow 24\cdot127 m\equiv 127\cdot124\pmod{127^2},$$
and then by cancelling a factor $127$ to
$$
24m\equiv124\pmod{127}.
$$
The inverse of $24$ modulo $127$ is $90$, so the unique solution of this is
$$
m\equiv 90\cdot124\equiv 111\pmod{127}.
$$
This corresponds to the square root
$$
b=12+111\cdot127=14109.
$$
A: There is a way to compute square roots from an odd composite modulus without factoring the modulus.  The speed for the naive algorithm is
$Modulus^{1/2} \log_2 \log_2 modulus$
A jazzed up way, which is similar to Dixon's equivalent square method (or the Quadratic factoring method) can speed up the algorithm to
X(TimeToFactorASemiPrime)
If the modulus is composed of many primes (which seems to indicate several equivalent squares would be necessary to factor the modulus), this method may find one square root faster than factoring the modulus, but I haven't absolutely proved that.
The Wikipedia article (which hasn't been approved yet) describing the algorithm is at:
http://en.wikipedia.org/wiki/Wikipedia_talk:Articles_for_creation/Square_root_of_composite_modulus
This algorithm is an equation that find a square root, once an equivalent square has been find that includes the partial relation:
$r^{2}+2+r^{-2}$
so it is very like factoring the modulus, as all the articles on modular square roots say, but, in the case of many large primes in the modulus, this method may be quicker (to find one root) than factoring the modulus.
A: Check out Adolf Kunerth's 1878 modular square root algorithm that does succeed in taking a modular square root of a composite modulus if an associated quadratic equation of form Ax^2+Bx+C==SQUARE is solved.  It doesn't need to factor the modulus.
See the only two sources mentioning the algorithm at
Adolf Kunerth, "Academie Der Wissenschaften" vol 78(2), 1878, p 327-338 (for quadratic equation algorithm), pp. 338–346 (for modular quadratic algorithm), available at Ernest Mayr Library, Harvard University
Leonard Eugene Dickson, "History of Numbers", vol 2, pp. 382–384
