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

  • $\begingroup$ 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$. $\endgroup$ – Peter Shor Jun 21 '19 at 1:22
  • $\begingroup$ @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: $\endgroup$ – orgesleka 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$, $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.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – orgesleka Jun 19 '19 at 18:40
  • $\begingroup$ The point with $\gcd(a_i,n)$ I can understand. I will see If I can "repair" this. $\endgroup$ – orgesleka Jun 19 '19 at 18:53
  • $\begingroup$ @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. $\endgroup$ – D.W. Jun 19 '19 at 18:57
  • $\begingroup$ ok thanks for your input $\endgroup$ – orgesleka Jun 19 '19 at 18:59
  • $\begingroup$ Thanks again for your answer. I updated the question. Maybe you can take a look? $\endgroup$ – orgesleka Jun 19 '19 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.