# Show that $\text{FACTORING} \le_P \text{SQROOT}$

I tried to prove that $$\text{FACTORING} \le_P \text{SQROOT}$$ in a general setting, so $$n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}$$.

THEOREM:Let $$n$$ be a composite number and let $$x$$ and $$y$$ be integers such that $$x^2 \equiv y^2 \pmod n$$ and $$x \not \equiv \pm y \pmod n$$ holds. Then $$\gcd(x+y, n)$$ and $$\gcd(x-y, n)$$ are non-trivial divisors of $$n$$.

My attempt:

$$\text{FACTORING} \le_P \text{SQROOT}$$: Suppose we have an algorithm $$\mathcal{A}$$ that solves $$\text{SQROOT}$$. We show that we can then factor $$n$$ with prime factorisation $$n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}$$. Select a random $$x \in Z/nZ$$ with $$\gcd(x,n) = 1$$. Compute $$a = x^2 \pmod n$$ and use $$\mathcal{A}$$ to find a square root $$y$$ of $$a$$ modulo $$n$$. If $$y \equiv \pm x \pmod n$$ choose another $$x$$ and repeat this process until a $$y$$ with $$y \not \equiv \pm x \pmod n$$ is found. Since there are $$2^k$$ distinct square roots of $$a$$ modulo $$n$$ the chance that said procedure needs to be repeated is $$\frac{1}{2^{k-1}}$$. So by the theorem above we can find two non-trivial divisors of $$n$$ in expected polynomial time. Repeating this procedure for the thus found factors of $$n$$ we can find the prime factorisation of $$n$$ in expected polynomial time.

I am a bit unsure about the whole "expected polynomial time" thing. I have only heard informal definitions of it until now. Could you please have a look at my proof?

EDIT: I initially accepted the answer of Meir Maor below, but there was a gap in it as I just realised:

$$k=2$$ is the worst case. But this implies only that $$n=p_1^{\alpha_1}p_2^{\alpha_2}$$, not $$n=p_1 p_2$$. So we still have to find some non-trivial divisors of the thus found factors of $$n$$ to get $$p_1$$ and $$p_2$$. I would like to keep the rigour of Meir Maor's answer, but I do not know how to determine the runtime of this procedure. Could you help me?

• Can you compute the probability that the factoring algorithm succeeds in terms of the probability that $\mathcal A$ succeeds? Interpret a series of independent trials as a negative binomial distribution; what's the expected number of trials, or the expected cost to execute the machine for that many trials? Nov 27, 2019 at 23:31
• Sorry but I do not get what you are trying to say. What is a NEGATIVE binomial distribution? Nov 28, 2019 at 8:58
• The negative binomial distribution is the distribution on the number of independent Bernoulli trials before a certain number of successes (or the number of failures before a certain number of successes, depending on how you parametrize it; beware fence posts). Here a Bernoulli trial is a run of your algorithm, which has some specific success probability that you can compute in terms of the success probability of $\mathcal A$, and you want to know the expected number of trials before a single success of the combined algorithm. Nov 28, 2019 at 14:41

Your proof is essentially correct. You may improve rigor by either calculating exactly or giving a bound on it's expected runtime.

If we take the simple case(which is also the worst case) where k=2 we get a probability of 1/2 to get a different root.

It should be noted that since our root x was uniformly random over Z/nZ it is also uniformly random over the roots of a. And therefor the probability of success at each attempt is 1/2 regardless of how our SQROOT algorithm chooses which root to provide.

If the probability is 1/2 per iteration the expected number of iterations is 2. This can be as 1/2+1/4+1/8... With probability 1/2 it takes 1 iteration with probability 1/4 it takes exactly 2 (fail, success) with probability 1/8 it takes exactly 3 (fail,fail, success) etc.

For k>2 the probability of success only increases and the expected invocation count is lower.

Therefor the expected runtime is 2 invocations of SQROOT + O(log(n)). The additional element is for the gcd and random selection part (or even receiving input and giving output).

• I am sorry to bother you again but there is a gap in your argumentation. You are right that $k=2$ is the worst case. But this implies only that $n=p_1^{\alpha_1}p_2^{\alpha_2}$, not $n=p_1 p_2$. So we still have to find some non-trivial divisors of the thus found factors of $n$ to get $p_1$ and $p_2$. But how could I express this with a bit more rigour? Dec 8, 2019 at 23:00
• Though we still have multiple roots. We have at least 2 roots which is sufficient. Dec 9, 2019 at 4:53
• Ok I think I got it now thanks again. Dec 9, 2019 at 9:56