# Is it possible to prove that a general purpose integer factorization algorithm must contain a loop?

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 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..".

• Does the quadratic sieve algorithm satisfy your assumptions? For the quadratic sieve, the running time $f(e)$ is small enough that $1 - (1-1/\sqrt{2^e})^{2 f(e)} \rightarrow 0$ as $e \rightarrow \infty$. Jun 21 '19 at 1:22
• @PeterShor: I know what you mean, this is a weakness in the argument. However I could do a refined analysis, which maybe you will find useful:
– user35803
Jun 21 '19 at 6:34

It depends on the precise model of computation you work within. However, this doesn't seem to be a useful direction for proving lower bounds on the time to factor.

# Uniform algorithms

Let's look at uniform algorithms. Suppose our model of computation is a Turing machine or the transdichotomous model or something similar, where each step can do at most a constant amount of work (or a logarithmic amount of work). Then any such algorithm must contain a loop or backward branch.

(Why? Such an algorithm must work on inputs of all possible lengths. The algorithm has finite length, say length $$k$$. If there are no loops or backward branches, then this means that any execution of the algorithm must involve at most $$k$$ steps, where $$k$$ is fixed. This means there exists $$n$$ large enough so that, when the input is $$n$$ bits long, the algorithm can't even read the entire input using $$k$$ steps of computation. Consequently, any such algorithm without loops cannot possibly be correct on all inputs.)

This doesn't seem useful for proving non-trivial lower bounds on the complexity of factoring.

# Non-uniform algorithms

Non-uniform algorithms don't require loops. In particular, if there is a non-uniform algorithm (possibly with loops) that takes $$T(n)$$ time on $$n$$-bit inputs, then there is a non-uniform algorithm without loops that takes $$O(T(n)^2)$$ time on $$n$$-bit inputs and has size $$O(T(n)^2)$$.

(Why? Simply unroll all loops. Since the algorithm takes $$T(n)$$ time, each loop will execute at most $$T(n)$$ times, so you can unroll it and make $$T(n)$$ copies.)

# Other notes

Your question claims "there must be an if-then statement which tests if $$1, $$x|n$$ or any other mathematically equivalent test", but this claim is not justified and I don't think it is correct. There could be algorithms that contain a loop with some other loop condition. Also, your heuristic is clearly false. The output of $$\gcd(a_i,n)$$ isn't anything like a uniformly distributed number from $$\{1,\dots,n\}$$. So the direction you're taking seems like it is based on faulty premises and seems like a dead end.

• Well if there is not if-then which tests if $1 < x < n$ and $1 < \gcd(x,n) < n$ or any_other_mathematically_equivalent_statement then how is the algorithm going to decide if it has found a solution?
– user35803
Jun 19 '19 at 18:40
• The point with $\gcd(a_i,n)$ I can understand. I will see If I can "repair" this.
– user35803
Jun 19 '19 at 18:53
• @orgesleka, just because you cannot imagine any other way to do it doesn't mean there is no other way to do it. That's not how proofs work. I wouldn't bother spending any time trying to repair this. It seems like a dead end.
– D.W.
Jun 19 '19 at 18:57
• ok thanks for your input
– user35803
Jun 19 '19 at 18:59
• Thanks again for your answer. I updated the question. Maybe you can take a look?
– user35803
Jun 19 '19 at 19:54