An heuristic argument why factoring is difficult

Let \(n=pq\) be the prime decomposition of \(n\) and let \(n=2^e\). Let us suppose that \(p = q = \sqrt{n}\). Let \(p_n\) be the probability to have a number \(1 \le x \le n\) with \(1 < gcd(x,n) < n\) and as such to also have a non-trivial factor of \(n\). Then we have \[p_n = 1-\frac{\phi(n)}{n}=1-\prod_{p|n}{(1-\frac{1}{p})} = 1-(1-\frac{1}{p})(1-\frac{1}{q}) \] \[ = 1-(1-\frac{1}{\sqrt{n}})^2 = 1-(1-\frac{1}{\sqrt{2^e}})^2 \] Suppose there exists a factoring-algorithm which runs in polynomial time \(f(e)\) and which draws a number \(x\) at every step and computes \(gcd(x,n)\). Let \(X\) be the number of numbers \(x\) with \(1 \lt x \lt n\) and \(1 \lt gcd(x,n) \lt n\) which the algorithm finds after \(f(e)\) steps. Then by definition of the algorithm we must have \[ 1 = P(X \ge 1) \] But on the other hand we have \[ P(X\ge 1) = 1 - P(X=0) = 1 - (1-p_n)^{f(e)} \] \[= 1-(1-\frac{1}{\sqrt{2^e}})^{2 \cdot f(e)} \] The last equality is by definition of the algorithm valid for every \(e\). But for \(e \rightarrow \infty\) we have \[1 = P(X \ge 1) = 1-(1-\frac{1}{\sqrt{2^e}})^{2 \cdot f(e)} \rightarrow_{e \rightarrow \infty} 0\] hence for \(e \rightarrow \infty\) we have the contradiction \(1 = 0\).