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?

Answer 1

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}$.