<p>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 <a href="https://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring">An NP-complete variant of factoring.</a></p>

<p>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?</p>

<p><strong>Update:</strong> 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?</p>

CC BY-SA 3.0
2015-08-15T07:39:10.790Z
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
CC BY-SA 3.0
2015-08-15T08:03:20.890Z
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
CC BY-SA 3.0
2015-08-15T08:23:30.457Z
I think removing Cramer's conjecture in the reduction is unlikely.
Turbo
<cc.complexity-theory><nt.number-theory><np-complete><factoring><undecidability>
Consequences of polynomial time algorithm to variant of integer factorization
Turbo
# Consequences of polynomial time algorithm to variant of integer factorization

(Asked by: username_0 on 2015-08-14)

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.](https://cstheory.stackexchange.com/questions/4769/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?

**Tags:** cc.complexity-theory, nt.number-theory, np-complete, factoring, undecidability

> **Comments:**
> **username_0**: I have a modified cramer's conjecture (note that I have used $k$-almost prime instead of prime). Read comments in attached stackexchange link.  
> **username_0**: 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.  
> **username_0**: I think removing Cramer's conjecture in the reduction is unlikely.  

---

## 0 answers

