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?
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).