Consequences of polynomial time algorithm to variant of integer factorization

Question

Given $N,U,V\in\Bbb N$ is there $n\in[U,V]\cap\Bbb N$ such that $n|N$ is $\mathsf{NP}$-complete modulo Cramer's conjecture on prime gaps is shown in An NP-complete variant of factoring.

So supposing status of Cramer's conjecture remains uncertain (that is it is not known to be true/false or undecidable), then is there any consequence of polynomial time algorithm to this variant factoring problem assuming that Cramer's conjecture cannot be removed from the reduction? That is could such an algorithm be of any value other than breaking RSA and some number theory problems? Could we use this algorithm to solve other problems in $\mathsf{NP}$. Would this still imply at least $\mathsf{NP}\subseteq\mathsf{RP}$? Where in Impagliazzo's five worlds would we be in?

Update: What is minimum number of distinct primes one needs in $N$ for completeness of this problem under Cramer's conjecture? How many such numbers are there?

I have a modified cramer's conjecture (note that I have used $k$-almost prime instead of prime). Read comments in attached stackexchange link. — Turbo, Aug 15 '15 at 07:39
Can you be more specific? $;;;$ There are 49 comments at that link, and I have no clue how any of them would yield implications from $:$ P = NP $;$. $;;;;;;;;$ — , Aug 15 '15 at 07:45
If $P=NP$, then there is a deterministic reduction from subset sum to this problem. Shouldn't this say gaps of primes are small? I could be wrong. This is the reasoning. — Turbo, Aug 15 '15 at 08:03
No. $:$ Such a reduction could just consist of solving the subset sum instance and then outputting some otherwise-arbitrary instance of this problem with the same answer. $;;;;$ — , Aug 15 '15 at 08:11
I think removing Cramer's conjecture in the reduction is unlikely. — Turbo, Aug 15 '15 at 08:23

score 3 · Accepted Answer · edited Apr 13 '17 at 12:57

ZPP = NP is a "consequence of polynomial time algorithm to this variant factoring problem", which can be deduced by replacing Cramer's conjecture with zero-error randomness,
rather than just removing Cramer's conjecture. Accordingly, we would be in Algorithmica.

One can simply test randomly chosen numbers in the relevant intervals
for primality, rather than choosing them deterministically.

Unless NP $\hspace{-0.02 in}\subseteq$ BQSUBEXP infinitely often, one needs [input_length]$^{\hspace{.03 in}\Omega \hspace{.02 in}(1)}$ distinct primes
"in $N$ for completeness of this problem under Cramer's conjecture",
since Shor's algorithm can be used to find the prime factors, and given those,
this problem can be solved by trying the products of each submultiset of those primes.
There are lots of such numbers, since there are lots of primes.

Products of n distinct $\big[$primes less than $2^{\hspace{.02 in}n}\hspace{-0.03 in}\big]$ are less than $2^{\hspace{.02 in}n^2}\hspace{-0.06 in}$, so their number of distinct prime factors is not less than [their_length]$^{1/2}$. According to wikipedia, since 2 is the only power of 2 that's prime, if 6 ≤ n then $\big[$the number of primes less than $2^{\hspace{.02 in}n}\hspace{-0.03 in}\big]$ is greater than $\dfrac{2^{\hspace{.02 in}n}}{\ln \hspace{-0.03 in}\left(2^{\hspace{.02 in}n}\right)\hspace{-0.03 in}+\hspace{-0.03 in}2}$.

For all n, if 20 ≤ n then $\ln \hspace{-0.03 in}\left(2^{\hspace{.02 in}n}\right)\hspace{-0.03 in}+\hspace{-0.03 in}2 \: = \: (n\hspace{-0.03 in}\cdot \hspace{-0.03 in}\ln(2))+2 \: = \: (\ln(2)\hspace{-0.03 in}\cdot \hspace{-0.03 in}n)+2 \: < \: \Big(\hspace{-0.05 in}\frac7{10}\hspace{-0.03 in}\cdot \hspace{-0.03 in}n\hspace{-0.04 in}\Big)+2 \: \leq \: \Big(\hspace{-0.05 in}\frac7{10}\hspace{-0.03 in}\cdot \hspace{-0.03 in}n\hspace{-0.04 in}\Big)+\Big(\hspace{-0.05 in}\frac1{10}\hspace{-0.03 in}\cdot \hspace{-0.03 in}n\hspace{-0.04 in}\Big) \: = \: \frac45 \cdot n \;\;\;$.

For all n, if 20 ≤ n then $\: \dfrac{5\hspace{-0.05 in}\cdot \hspace{-0.05 in}\left(2^{\hspace{.02 in}n-2}\hspace{-0.05 in}\right)}n = \dfrac{\frac54 \hspace{-0.05 in}\cdot \hspace{-0.03 in} 2^{\hspace{.02 in}n}}n = \dfrac{2^{\hspace{.02 in}n}}{\frac45 \hspace{-0.05 in}\cdot \hspace{-0.03 in}n} < \dfrac{2^{\hspace{.02 in}n}}{\ln \hspace{-0.03 in}\left(2^{\hspace{.02 in}n}\right)\hspace{-0.03 in}+\hspace{-0.03 in}2}$.

For all n, if 20 ≤ n then there are more than $\dfrac{5\hspace{-0.05 in}\cdot \hspace{-0.05 in}\left(2^{\hspace{.02 in}n-2}\hspace{-0.05 in}\right)}n$ primes less than $2^{\hspace{.02 in}n}$.

For each such n, one can choose n disjoint sets of at least $\left\lfloor \hspace{-0.05 in} \dfrac{5\hspace{-0.05 in}\cdot \hspace{-0.05 in}\left(2^{\hspace{.02 in}n-2}\hspace{-0.05 in}\right)}{n^{\hspace{.02 in}2}}\hspace{-0.04 in} \right\rfloor$ of those primes.

For all n, if 20 ≤ n then $\;\;\; \dfrac{2^{\hspace{.02 in}n}}{n^{\hspace{.02 in}2}} \: = \: \dfrac{4\hspace{-0.05 in}\cdot \hspace{-0.05 in}\left(2^{\hspace{.02 in}n-2}\hspace{-0.05 in}\right)}{n^{\hspace{.02 in}2}} \: < \: \dfrac{\left(4\hspace{-0.05 in}\cdot \hspace{-0.05 in}\left(2^{\hspace{.02 in}n-2}\hspace{-0.05 in}\right)\right)+2^{\hspace{.02 in}n-2}\hspace{-0.04 in}-n^2}{n^{\hspace{.02 in}2}}$

$= \: \dfrac{4\hspace{-0.05 in}\cdot \hspace{-0.05 in}\left(2^{\hspace{.02 in}n-2}\hspace{-0.05 in}\right)}{n^{\hspace{.02 in}2}} \: < \: \dfrac{\left(5\hspace{-0.05 in}\cdot \hspace{-0.05 in}\left(2^{\hspace{.02 in}n-2}\hspace{-0.05 in}\right)\right)\hspace{-0.02 in}-n^2}{n^{\hspace{.02 in}2}} \: = \: \dfrac{5\hspace{-0.05 in}\cdot \hspace{-0.05 in}\left(2^{\hspace{.02 in}n-2}\hspace{-0.05 in}\right)}{n^{\hspace{.02 in}2}}-1 \: < \: \left\lfloor \hspace{-0.05 in} \dfrac{5\hspace{-0.05 in}\cdot \hspace{-0.05 in}\left(2^{\hspace{.02 in}n-2}\hspace{-0.05 in}\right)}{n^{\hspace{.02 in}2}}\hspace{-0.04 in} \right\rfloor \;\;\;$.

For all n, if 20 ≤ n then one can choose n disjoint sets of at least $\dfrac{2^{\hspace{.02 in}n}}{n^{\hspace{.02 in}2}}$ primes less than $2^{\hspace{.02 in}n}$.

For all n, if 20 ≤ n then at least $\bigg(\hspace{-0.04 in}\dfrac{2^{\hspace{.02 in}n}}{n^{\hspace{.02 in}2}}\hspace{-0.06 in}\bigg)^{\hspace{-0.04 in}n}$ number less than $2^{\hspace{.02 in}n^2}$ have n distinct prime factors.

For all n, $\; \bigg(\hspace{-0.04 in}\dfrac{2^{\hspace{.02 in}n}}{n^{\hspace{.02 in}2}}\hspace{-0.06 in}\bigg)^{\hspace{-0.04 in}n} = \dfrac{\left(2^{\hspace{.02 in}n}\hspace{-0.02 in}\right)^n}{\left(\hspace{-0.02 in}n^{\hspace{.02 in}2}\hspace{-0.04 in}\right)^{\hspace{-0.02 in}n}} = \dfrac{2^{\hspace{.02 in}n\cdot n}}{n^{\hspace{.02 in}2\cdot n}} = \dfrac{2^{\hspace{.02 in}n^2}}{n^{\hspace{.02 in}2\cdot n}} \:\:$.

Therefore, for all n, if 20 ≤ n then at least $\dfrac{2^{\hspace{.02 in}n^2}}{n^{\hspace{.02 in}2\cdot n}}$ numbers less than $2^{\hspace{.02 in}n^2}$ are
such that their number of distinct prime factors is not less than [their_length]$^{1/2}$.

do you mean this http://mathoverflow.net/questions/212816/are-there-effective-small-intervals-in-which-primes-are-dense? Could you add your knowledge on replacing Cramer's conjecture in a more down to earth way? — Turbo, Aug 20 '15 at 04:02
I believe 'effective result' is defined in the same way as "constructive result", although the term 'effective' would be used far less often in continuous math. — , Aug 20 '15 at 04:53
Could you give an estimate on 'lots of such numbers'? Your 'effective' result is still vague otherwise I am happy with your post. — Turbo, Aug 20 '15 at 04:55
ah ever in you use 'zero error randomness' instead of cramer's conjecture, do you have implication $NP\subseteq BQSUBEXP$ if number of distinct primes is much smaller than quoted estimate in your post? — Turbo, Aug 20 '15 at 05:39
Yes. Even ZPP can carry out the reduction, so BQSUBEXP can also carry out the reduction. — , Aug 20 '15 at 05:41
So supposing this problem is in $P/Poly$, then does $NP\subseteq P/Poly$ hold (since $ZPP\subseteq BPP\subseteq P/Poly$ holds)? — Turbo, Aug 21 '15 at 00:46
Well, I think the mere results $: ZPP\subseteq BPP\subset P/poly :$ aren't enough, but from the proof of $: BPP\subseteq P/poly :$, $:$ one can conclude that $: NP\subseteq P/poly :$ would hold if this problem is in $P/poly$. $;;;;$ — , Aug 21 '15 at 01:08
That is right, but there is no analogue in Impagliazzo's world right? This would be something else? — Turbo, Aug 21 '15 at 12:20
"there is no analogue" of what "in Impagliazzo's world"s? $;$ — , Aug 21 '15 at 12:23
Analogue to fact $NP\subseteq P/Poly$ or similar hierarchy collapse results? — Turbo, Aug 21 '15 at 12:25
The analogue to $: NP \subseteq P/poly :$ for Impagliazzo's worlds would be that we're not in Minicrypt or Cryptomania with respect to non-uniform adversaries. $;;;;$ — , Aug 21 '15 at 12:28
As you mentioned we need [input_length]$^{\hspace{.03 in}\Omega \hspace{.02 in}(1)}$ distinct primes. If [input length] is $\log_2 n$ bits, could the primes be as small as ${\hspace{.03 in}o\hspace{.02 in}((\log_2 n)^{\frac1k})}$ where $6>(\log_2 n)^{\frac1k}$ or $k>\frac{\log_2(\log_2n)}{\log_26}$? — Turbo, Sep 07 '15 at 18:55
Those conditions each force $k$ to converge to $\infty$. $;$ — , Sep 08 '15 at 02:16
Yes, since only $:o\hspace{-0.04 in}\left(\hspace{-0.05 in}(\log(n))^{\frac1k}\hspace{-0.07 in}\right):$ primes are as small as $:o\hspace{-0.04 in}\left(\hspace{-0.05 in}(\log(n))^{\frac1k}\hspace{-0.07 in}\right);$. $;;;;$ — , Sep 08 '15 at 06:40
yes that is indeed correct. so how small can the primes be if all are of same size? — Turbo, Sep 08 '15 at 16:13
I dont get it. Say input number $N$ has $\log N$ bits. And $N=p_1^{e_1}\dots p_t^{e_1}$. You mentioned $t=(\log N)^{\Omega(1)}$. How can each prime be of length $\log p_i=(\log N)^{\Omega(1)}$ as well? — Turbo, Sep 09 '15 at 15:06
I was referring to the reduction, where "the input" is the instance of an NP problem. $\hspace{.44 in}$ (Although, actually, that doesn't matter, since the number of primes could just $\hspace{1.16 in}$ be the same as the length of each prime.) $;$ — , Sep 09 '15 at 20:00
That is why I am wondering what is the largest size of primes if all primes are of equal size (for case $e_i=1$) for the reduction to still hold NP hardness? — Turbo, Sep 09 '15 at 22:42
@RickyDemer Do you know how big $\log_2U-\log_2L$ can be for the problem to remainNP complete if Cramer's conjecture holds true? Is the difference bounded above by constants? — , Oct 07 '15 at 09:22

Consequences of polynomial time algorithm to variant of integer factorization

1 Answers1