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?
Best Answer
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. $$