# What are the current known implications of the complexity of Integer Factorization?

According to my limited knowledge we know that since Integer Factorization lies in the intersection of NP and co-NP it cannot be NP-complete unless NP=co-NP. However, do we know any other implications yet- like if P != NP, does this mean that Integer Factorization is necessarily not in P? Conversely, if Integer Factorization is in P, does this imply anything about the polynomial hierarchy? Thanks.

• Not 100% sure, but I think the gist is that we don't know much. The fact that primality testing is in $P$ with such a high exponent has led some people to belive that factorization might be in $P$, but I don't actually have a reference for this, I just remember hearing it somewhere, so I could be wrong. – jmite Jul 17 '14 at 16:57
• @jmite, I don't think anyone conjectures that factoring is in $P$. You are right that we don't know much. – D.W. Jul 18 '14 at 5:50

Before answering your questions a distinction has to be made, when talking about $NP$ completeness we are talking about the decision problem not the function problem, which is given an integer N and an integer M with 1 ≤ M ≤ N, does N have a factor d with 1 < d < M.
So answering your questions in order, Since integer factorization is not known to be NP complete, $P \neq NP$ would not cause it to automatically not be in $P$ since quite often things that were thought to be in $NP$ are moved to $P$, only an $NP$ complete problem would be excluded from being in $P$. For the second one, again since it is not $NP$ complete a polynomial time solution to it will not effect the hierarchy for the same reason as before.
As an extra note, the actual location of factorization in the hierarchy is unknown, we know is is $BQP$, $NP$, $co-NP$, $FNP$ and $UP$. It may end up being $NP$-Intermediate, but no one knows for sure.
• If you really want to get technical then yes, it is not known to be NP complete, also it is not believed to be. Current thoughts say that if $P\neq NP$ then it is not in P, NP complete, or co NP Complete. I'm not sure I follow on how you reached your conclusion though. Even if $P=NP$ not all problems would be in what was previously the NP complete category. – lPlant Jul 18 '14 at 2:18