1) Let $A$ be a (general purpose) algorithm that factors $n$. Suppose $A$ contains a loop (which is hard to imagine if not impossible that it does not.) If $A$ contains nested loops then these loops can be combined to one loop. If $A$ contains more loops in sequence, then these loops can also be combined to one loop. So suppose that $A$ contains exactly one loop. Since $A$ must finish the factorization after finitely many steps and output $x$ with $1 < x < n$, $x|n$, there must be an if-then statement which tests if $1 < x < n$, $x|n$ or any other mathematically equivalent test. Hence in each step $1,\cdots,t$ we have a number $a_i \in \mathbb{N}$ which is tested. But then letting $g_i = \gcd(a_i,n)$ we have $1 \le g_i \le n$. It could happen that $g_i = g_j$ for $i \neq j$.
Heuristic: We imagine that the numbers $g_i$ are drawn with replacement from the urn $\{1,\cdots,n\}$.
2) Let $n=pq$ be the prime decomposition of $n$ and let $n=2^e$. Let us suppose that $p \equiv q \equiv \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)$ which draws with replacement a number $x$ 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$.
My question is, if someone has an idea how to replace the condition $p \equiv q \equiv \sqrt{n}$ with a more rigorous condition. My second question is, how does one prove, that no (general purpose) factoring algorithm can do without a loop? Maybe using Kolmogorov complexity of the primes to be factored?
Edit: As @D.W. pointed out the heuristic with $g_i$ is clearly wrong. What I meant to write is that we imagine that the $a_i$ are chosen with replacement from the urn $\{m,m+1,\cdots,M-1,M\}$, where $ m = \min_i(a_i), M = \max_i(a_i)$. Let $N= M-m+1$ and $N_1 = |\{ k | m \le k \le M, \gcd(k,n)=1 \text{ or } \gcd(k,n)=n\}|$. Then the probability $p_n$ to have a non-trivial factor of $n$ is $p_n = 1 - \frac{N_1}{N}$ If $X$ counts the number of successes of the algorithm , then by definition of the algorithm we must have: $$1 = P(X \ge 1) = 1-P(X=0) = 1-(1-p_n)^t$$ Now for this argument to be valid, one would need a number theoretic formula for $N_1$. Also what I meant with loop is not the reading of the number $n$ but a loop for "the search for the solution". If there is such a loop which produces the numbers $a_1,\cdots,a_t$ then there must be a criterion to stop the loop after $t$ steps. The loop will terminate earliest when an $x$ ( a solution) such that $1<x<n$ and $1 < \gcd(n,x) < n$ is found. So in this fashion, one might see the statement, "there must exist an if-then statement such that..".
