0
$\begingroup$

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

$\endgroup$
2
  • $\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$ Jun 21, 2019 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$
    – user35803
    Jun 21, 2019 at 6:34

1 Answer 1

1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.