3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Emil Jeřábek Jun 24 '18 at 10:05
  • $\begingroup$ "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? $\endgroup$ – Gerry Myerson Jun 24 '18 at 12:09
  • $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek Jun 27 '18 at 11:51
  • $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Jun 27 '18 at 14:20
  • $\begingroup$ I meant $(\alpha\sqrt N,\beta\sqrt N)$. $\endgroup$ – Emil Jeřábek Jun 27 '18 at 14:41

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.