# Factoring problem similar to $RSA$ structure that is possibly not $NP$ complete and not $coNP$ also?

Standard factoring problem $\Pi_1$ is 'Given integers $N$ and $M$ is there a factor $d\in[1,M]$ of $N$?'. This is in $NP$ since such a factor is the witness and in $coNP$ since one can check all the prime factors of $N$ are bigger than $M$. So the standard factoring problem $\Pi_1$ is in $NP\cap coNP$.

Factoring problem $\Pi_2$ 'Given integers $N,L,U$ is there a factor $d\in[L,U]$ of $N$?' is $NP$-complete under Cramer's conjecture of prime gaps. So factoring problem $\Pi_2$ cannot be in $coNP$ under standard conjectures.

Factoring problem variant $\Pi_3$ 'Given integers $N$ is there $d_1,d_2\in\mathbb Z$ such that $$\sqrt N<\gamma(d_2-d_1),\quad d_1<d_2<\delta d_1\quad\mbox{ and }\quad d_1d_2=N$$ holds where $1<\gamma,\delta$ are constants?' is clearly in $NP$ and it generalizes $RSA$ type factoring problem as we will explain shortly. However it is neither clear if $\Pi_3$ is in $coNP$ nor clear if $\Pi_3$ is $NP$ complete problem.

1. Is $\Pi_3$ in $coNP$?

If $\Pi_1\in P$ then $\Pi_2$ could still be not in $P$ since it is $NP$ complete under a believable conjecture.

1. If $\Pi_1\in P$ does it help decide $\Pi_3$?

Note that if $d_1,d_2$ are prime then $\Pi_3$ includes some $RSA$ type problems and if $d_1,d_2$ are prime then $\Pi_3$ is in $coNP$ and if $\Pi_1\in P$ then $\Pi_3\in P$ holds.

• What do you mean by "RSA type problems"? Are you just saying that $\Pi_3$ includes factoring of Blum integers as a special case, or is there more to it? – Emil Jeřábek Jun 24 '18 at 10:05
• "Given integers $N,L,U$ is there a factor $d\in[U,V]$ of $N$" I suppose $L$ and $V$ are supposed to be the same? – Gerry Myerson Jun 24 '18 at 12:09
• As far as I can see, $\Pi_3$ is trivial to compute as written, because the answer is always NO: if I write $d_2=d$ and $d_1=N/d$, the second condition is equivalent to $\sqrt N<d<\sqrt{2N}$, and the first condition to $d^2-d\sqrt N-N>0$, which resolves to $d>\frac{1+\sqrt5}2\sqrt N$. However, these conditions are contradictory, as $\sqrt2<\frac{1+\sqrt5}2$. – Emil Jeřábek Jun 27 '18 at 11:51
• No, I mean $\sqrt{2N}$: $d_2<2d_1\iff d<2N/d\iff d^2<2N\iff d<\sqrt{2N}$. Anyway, since any conditions of this sort are equivalent to “$N$ has a divisor in $(\alpha N,\beta N)$” for certain constants $\alpha,\beta$, why don’t you just write it that way? It would be much more clear. – Emil Jeřábek Jun 27 '18 at 14:20
• I meant $(\alpha\sqrt N,\beta\sqrt N)$. – Emil Jeřábek Jun 27 '18 at 14:41