<p>No, its not known to be NP-complete, and it would be very surprising if it were. This is because its decision version is known to be in $\text{NP} \cap \text{co-NP}$. (Decision version: Does $n$ have a prime factor $\lt k$?)</p>

<p>It is in NP, because a factor $p \lt k$ such that $p \mid n$ serves as a witness of a yes instance.</p>

<p>It is in co-NP because a prime factorization of $n$ with no factors $\lt k$ serves as a witness of a no instance. Prime factorizations are unique, and can be verified in polynomial time because testing for primality is in P. </p>

CC BY-SA 3.0
2014-07-15T20:58:11.510Z
wouldn't that be all not most NP complete algorithms do not have P-time quantum algorithms, give the NP complete reduction?
Simon
CC BY-SA 3.0
2016-09-26T17:10:23.143Z
Can you explain why it will be "surprising" if $\text{NP}\subseteq \text{NP}\cap \text{co-NP}$?
Jus12
CC BY-SA 2.5
2010-08-17T15:54:52.360Z
yes; apparently, Shor's algorithm can be used to solve it in polynomial time on a quantum computer, whereas iirc. most NP complete algorithms did not have P-time quantum versions.
gatoatigrado
CC BY-SA 2.5
2010-08-17T15:41:49.103Z
2011-02-07T09:54:08.053Z
2011-02-07T09:54:08.053Z
Aaron Roth
<blockquote>
  <p><strong>Possible Duplicate:</strong><br>
  <a href="https://cstheory.stackexchange.com/questions/167/what-are-the-consequences-of-factoring-being-np-complete">What are the consequences of factoring being NP-complete?</a>  </p>
</blockquote>



<p>What notable reference works have covered this?</p>

CC BY-SA 2.5
2011-02-08T09:49:14.997Z
I am closing this question as a duplicate of a question the OP has asked based on Moritz's comment above: [What are the consequences of factoring being NP-complete?](http://cstheory.stackexchange.com/questions/167/what-are-the-consequences-of-factoring-being-np-complete)
Kaveh
CC BY-SA 3.0
2015-07-19T20:40:32.233Z
@Calmarius I guess 5 years' time passing can do that. :)
Daniel Apon
CC BY-SA 3.0
2015-07-19T21:05:08.587Z
RE @Calmarius "And the linked duplicate doesn't answer this question" -- The answer to the question "Is integer factorization NP-complete?" is: "We don't know, but it seems unlikely, as integer factorization being NP-complete implies other unlikely things."
Daniel Apon
CC BY-SA 3.0
2015-07-05T20:46:21.637Z
@DanielApon searching for the term "integer factorization np complete" in Google brings up this page as a first result, for me now. And the linked duplicate doesn't answer this question.
Calmarius
CC BY-SA 2.5
2010-08-17T15:50:58.727Z
http://en.wikipedia.org/wiki/Integer_factorization
Aaron Sterling
CC BY-SA 2.5
2010-08-17T16:00:28.597Z
No, it isn't, as detailed in Aaron's answer. However you may also be interested to know that the problem is contained in BQP, and there is a quantum algorithm for integer factorization which runs in time O(n^3) or less (depending on which multiplication algorithm is used to calculate the mod exponential).
Joe Fitzsimons
CC BY-SA 2.5
2010-08-17T16:12:51.990Z
I think this may be a more suitable question if rephrased as: "What are the consequences of factoring being NP-complete?" But as stated, it's all answered on the wikipedia page (btw, first hit on google for "integer factorization").
Moritz
CC BY-SA 2.5
2010-08-17T16:18:25.727Z
I believe Moritz's comment here is insightful, txwikinger.

Questions that, as asked, can be answered by a quick Wikipedia or Google search are outside the scope of this site (Disclaimer: This is my opinion, and appears to be the opinion of some others as well.). Variations on the theme that explicitly dig deeper into what is less readily available on the Internet already can be very useful however.
Daniel Apon
CC BY-SA 2.5
2010-08-17T16:31:02.627Z
@Daniel Apon: Well, I take the advise, however, it does not make sense to make a proposal in which this exact question is voted as on-topic without any counter votes, and then say it is off-topic. Somewhere there has to be some sanity, that people know what this site is about!
txwikinger
CC BY-SA 2.5
2010-08-17T16:47:54.870Z
Yes, I agree that it is a problem. Hopefully kinks like this will be ironed out as time passes. In general, though, I think the fear is that the site could degenerate to a place for students to ask homework questions if "less interesting" questions are allowed (for an appropriate interpretation of "less interesting"). One of the important goals is to promote advanced Q&A, since there has been a noticeable lack of this elsewhere for CS theory.
Daniel Apon
CC BY-SA 2.5
2010-08-17T16:50:34.353Z
I was a student long time ago, when most people here have probably not even been born :D

Anyway, joke aside. Taken what you said, it still does not resolve the issue, that the site was proposed on totally different terms than some people are pushing it now. We do not know if that is even a majority. You only need to have a gang of 5 to close questions. And it should also be considered if that way will lead to a long-term existence of this site. If the accepted audience shrinks to be too small, I doubt this site will ever leave the public beta.
txwikinger
<cc.complexity-theory><np-hardness><factoring>
Is integer factorization an NP-complete problem?
txwikinger
# Is integer factorization an NP-complete problem?

(Asked by: username_0 on 2010-08-17)

> **Possible Duplicate:**  
> [What are the consequences of factoring being NP-complete?](https://cstheory.stackexchange.com/questions/167/what-are-the-consequences-of-factoring-being-np-complete)

What notable reference works have covered this?

**Tags:** cc.complexity-theory, np-hardness, factoring

> **Comments:**
> **username_4**: http://en.wikipedia.org/wiki/Integer_factorization  
> **username_5**: No, it isn't, as detailed in Aaron's answer. However you may also be interested to know that the problem is contained in BQP, and there is a quantum algorithm for integer factorization which runs in time O(n^3) or less (depending on which multiplication algorithm is used to calculate the mod exponential).  
> **username_6**: I think this may be a more suitable question if rephrased as: "What are the consequences of factoring being NP-complete?" But as stated, it's all answered on the wikipedia page (btw, first hit on google for "integer factorization").  
> **username_2**: I believe username_6's comment here is insightful, username_0.  Questions that, as asked, can be answered by a quick Wikipedia or Google search are outside the scope of this site (Disclaimer: This is my opinion, and appears to be the opinion of some others as well.). Variations on the theme that explicitly dig deeper into what is less readily available on the Internet already can be very useful however.  
> **username_0**: @username_2: Well, I take the advise, however, it does not make sense to make a proposal in which this exact question is voted as on-topic without any counter votes, and then say it is off-topic. Somewhere there has to be some sanity, that people know what this site is about!  
> **username_2**: Yes, I agree that it is a problem. Hopefully kinks like this will be ironed out as time passes. In general, though, I think the fear is that the site could degenerate to a place for students to ask homework questions if "less interesting" questions are allowed (for an appropriate interpretation of "less interesting"). One of the important goals is to promote advanced Q&A, since there has been a noticeable lack of this elsewhere for CS theory.  
> **username_0**: I was a student long time ago, when most people here have probably not even been born :D  Anyway, joke aside. Taken what you said, it still does not resolve the issue, that the site was proposed on totally different terms than some people are pushing it now. We do not know if that is even a majority. You only need to have a gang of 5 to close questions. And it should also be considered if that way will lead to a long-term existence of this site. If the accepted audience shrinks to be too small, I doubt this site will ever leave the public beta.  
> **username_1**: I am closing this question as a duplicate of a question the OP has asked based on username_6's comment above: [What are the consequences of factoring being NP-complete?](http://cstheory.stackexchange.com/questions/167/what-are-the-consequences-of-factoring-being-np-complete)  
> **username_3**: @DanielApon searching for the term "integer factorization np complete" in Google brings up this page as a first result, for me now. And the linked duplicate doesn't answer this question.  
> **username_2**: @username_3 I guess 5 years' time passing can do that. :)  
> **username_2**: RE @username_3 "And the linked duplicate doesn't answer this question" -- The answer to the question "Is integer factorization NP-complete?" is: "We don't know, but it seems unlikely, as integer factorization being NP-complete implies other unlikely things."  

---

## 1 answers

### Answer by username_7 on 2010-08-17. Score: 38 | Accepted answer

No, its not known to be NP-complete, and it would be very surprising if it were. This is because its decision version is known to be in $\text{NP} \cap \text{co-NP}$. (Decision version: Does $n$ have a prime factor $\lt k$?)

It is in NP, because a factor $p \lt k$ such that $p \mid n$ serves as a witness of a yes instance.

It is in co-NP because a prime factorization of $n$ with no factors $\lt k$ serves as a witness of a no instance. Prime factorizations are unique, and can be verified in polynomial time because testing for primality is in P.

> **Comments:**
> **username_10**: yes; apparently, Shor's algorithm can be used to solve it in polynomial time on a quantum computer, whereas iirc. most NP complete algorithms did not have P-time quantum versions.  
> **username_8**: wouldn't that be all not most NP complete algorithms do not have P-time quantum algorithms, give the NP complete reduction?  
> **username_9**: Can you explain why it will be "surprising" if $\text{NP}\subseteq \text{NP}\cap \text{co-NP}$?  

---

