2
$\begingroup$

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?

  • 1
    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.2012-01-01

2 Answers 2

6

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

  • 0
    Adding for the sake of completeness that if $2$ is one of the prime factors, then it gets messier.2012-01-01
0

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.