I am posting this question here in hope that someone finds this heuristic useful, and maybe someone with more experience will make use of this:
As @GerryMyerson suggested here is a statement of what I am trying to prove: There is no "simplified" algorithm, which can factor integers in polynomial time. The word "simplified" is described in more detail below.
First notice that $\exists d: 1 < d < n , d | n$ is equivalent to $\exists x: 1 < \gcd(x,n) < n$.
Let $A$ be a general purpose factorization algorithm which in every step $1,\cdots,t$ draws a number without replacement $a_i \in \mathbb{N}$ from the urn $\{m_n,m_n+1,\cdots,M_n-1,M_n\}$ and tests if $ 1 < \gcd(a_i,n) < n$ ($A$ = "simplified" algorithm). Besides the heuristic, that the numbers are drawn without replacement, some general purpose algorithms operate this way, for example the Fermat - Factorization, trial divison, or even Quadratic sieve. The point here is that the algorithm generates "candidate" numbers $a_i$ in each step and tests if those number represent a "solution". Let $Y$ be the waiting time until the first $a_i$ is found with $1 < \gcd(a_i,n) < n$, after which the algorithm stopps and prints $\gcd(a_i,n)$. Let $d_n$ count the number of $k$, $m_n \le k \le M_n$ such that $1 < \gcd(a_k,n) < n$ and $N_n = M_n-m_n+1$. Then we will have $$d_n \approx N_n ( \frac{1}{p}+\frac{1}{q}-\frac{1}{n})$$ if $n=pq$ is the prime decomposition of $n$. Letting $$p \approx q \approx \sqrt{n}$$ we get $$d_n \approx N_n ( \frac{2}{\sqrt{n}}-\frac{1}{n})$$
The random variable $Y$ is negatively hypergeometrically distributed with expected value:
$$t = E[Y] = \frac{N_n+1}{d_n+1} \approx \frac{N_n}{d_n}$$
a) Suppose $t \le \log(n)^c$ is an upper bound on the expected runtime of the algorithm. Then:
$$ 1 \le \log(n)^c (\frac{2}{\sqrt{n}}-\frac{1}{n}) \rightarrow 0$$ for $n \rightarrow \infty$, which is impossible. Hence no such upper bound can exist.
b) If $t\le \sqrt{n}$ is an upper bound, then
$$ 1 \le \sqrt{n}(\frac{2}{\sqrt{n}}-\frac{1}{n}) = 2 - \frac{1}{\sqrt{n}} $$ which has for $n \rightarrow \infty$ limit $=2$ and hence no contradiction arises.
c) If $t \le \exp(\sqrt{\log(n)\log(\log(n))})$ then we will get similar to a) a contradiction $1 \le 0$. Hence sub-exponential time can not be reached with "simplified" algorithms. (Since Quadratic Sieve has sub-exponential time, this means, either that "simplified" algorithms are too restrictive, or that one has first to do a de-randomization, if possible, of the "simplified" algorithm.)
My question is, if you can think of better ways, more rigorous, to replace various steps in this heuristic with more robust arguments?
Thanks for your help!