# 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?

-
Find a square root mod $p$ and use Hensel's Lemma to lift to a square root mod $p^2$. – Brandon Carter Dec 31 '11 at 17:31
I'm missing something. I implemented the Hensel lemma as described at Wikipedia at http://codepad.org/tJCd8zhS. That correctly computes the modular square root of 2 with modulus 7^2 as in the example. But for my calculation, 13290059 == 15892 mod 127^2, my function computes 4711 and 11418 instead of the proper answers of 2020 and 14109. What have I done wrong? – user448810 Dec 31 '11 at 20:44
You computed the square roots of $17$ modulo $127^2$ instead of $15892$. When you do Hensel lifting you need to take into account that you really wanted to compute the square root of an element that is congruent to $17$ modulo $127$ - not the square root of $17$ itself. – Jyrki Lahtonen Jan 1 '12 at 8:17

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.$$

-
Got it. Coded solution at codepad.org/x4kr9SPc. Many thanks. – user448810 Jan 1 '12 at 12:08
@user448810, glad to hear that you got your code to work out correctly. Of course, it suffices to find one of the square roots as they are negatives of each other. For example, $14109\equiv-2020\pmod{127^2}$. – Jyrki Lahtonen Jan 1 '12 at 12:16
It doesn't matter for my purposes today, but does computing the modular square root with a composite modulus that is not a prime power involve factoring the modulus, computing the modular square roots relative to each factor, and combining them with the Chinese remainder theorem? – user448810 Jan 1 '12 at 15:35
@user448810: Yes, that's the idea. Do observe that you get more than two square roots then. 4 with two prime factors (CRT to all sign combinations), 8 with three etc. – Jyrki Lahtonen Jan 1 '12 at 18:02
Adding for the sake of completeness that if $2$ is one of the prime factors, then it gets messier. – Jyrki Lahtonen Jan 1 '12 at 21:45

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.

-