2
$\begingroup$

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!

$\endgroup$
8
  • $\begingroup$ There is no statement of what it is that you are trying to prove here. $\endgroup$ Jun 21, 2019 at 6:54
  • $\begingroup$ @GerryMyerson: I am trying to prove, that certain kind of "simplified" algorithms, can not do factorization fast. $\endgroup$
    – user6671
    Jun 21, 2019 at 6:56
  • 1
    $\begingroup$ What's missing is a simple, clear statement of the result you are trying to prove. $\endgroup$ Jun 21, 2019 at 6:57
  • $\begingroup$ @GerryMyerson: Ok thanks I changed this. $\endgroup$
    – user6671
    Jun 21, 2019 at 7:00
  • 1
    $\begingroup$ When you're not sure where to post, you post to one and then wait a week and if nothing happens then you post to the other. Also, when you do post to a second site, you post links at each site to the post at the other. $\endgroup$ Jun 23, 2019 at 9:21

0

Your Answer

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