<p>The textbook of <a href="http://www.math.sc.edu/~cooper/math778C/abct.pdf">Computational Complexity: Modern Approach</a>, by Arora and Barak gives such example: </p>

<p>They define the decision problem Integer Factoring on input of three positive integers,</p>

<p>$\text{Integer Factoring} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$.</p>

<p>They state that Alon and Kilian showed that if integer $p$ is not required to be prime number then the problem becomes $NP$-complete.</p>

CC BY-SA 3.0
2013-06-21T18:01:05.207Z
http://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring
Huck Bennett
CC BY-SA 3.0
2013-06-21T18:58:25.600Z
p.39 in other words "Given three numbers N, L, U decide if N has a prime factor p in the interval [L, U]. The certiﬁcate is the factor p." on p.58 it is stated the NP complete case is an unpublished result from personal communication. does anyone know if its ever been published?
vzn
CC BY-SA 3.0
2013-06-21T19:21:20.817Z
@vzn I don't believe that the proof has been published before. Personaly, I searched a lot for it with no luck.
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-06-05T14:39:16.143Z
@Anush I believe there are no updates
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-06-21T17:07:53.887Z
2013-06-21T17:07:53.887Z
Mohammad Al-Turkistany
<p>The exact complexity of factoring integers (the decision problem) is a major <a href="http://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity" rel="nofollow">open question</a> in TCS (with important implications, especially in cryptography because of the <a href="http://en.wikipedia.org/wiki/RSA_%28algorithm%29" rel="nofollow">RSA algorithm</a>), and is widely conjectured to lie "between" P and NP-complete (see the <a href="http://en.wikipedia.org/wiki/AKS_algorithm" rel="nofollow">AKS</a> algorithm and <a href="http://en.wikipedia.org/wiki/Shor%27s_algorithm" rel="nofollow">Shor's algorithm</a> for two other key aspects of its significance).</p>

<p>Yet, there is so much diversity among the NP-complete problems, including some relating to factoring types of objects and problems in number theory.</p>

<blockquote>
  <p>What are some of the "closest" or "nearest" NP-complete problems to integer factoring?</p>
</blockquote>

<p>Optionally, an answer might indicate why such problems are thought not to be equivalent to integer factoring under polynomial time reductions (even circumstantial evidence would be appreciated).</p>

<cc.complexity-theory><nt.number-theory><factoring>
What NP-complete problems are most similar to integer factoring?
vzn
# What NP-complete problems are most similar to integer factoring?

(Asked by: username_0 on 2013-06-21)

The exact complexity of factoring integers (the decision problem) is a major [open question](http://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity) in TCS (with important implications, especially in cryptography because of the [RSA algorithm](http://en.wikipedia.org/wiki/RSA_%28algorithm%29)), and is widely conjectured to lie "between" P and NP-complete (see the [AKS](http://en.wikipedia.org/wiki/AKS_algorithm) algorithm and [Shor's algorithm](http://en.wikipedia.org/wiki/Shor%27s_algorithm) for two other key aspects of its significance).

Yet, there is so much diversity among the NP-complete problems, including some relating to factoring types of objects and problems in number theory.

> What are some of the "closest" or "nearest" NP-complete problems to integer factoring?

Optionally, an answer might indicate why such problems are thought not to be equivalent to integer factoring under polynomial time reductions (even circumstantial evidence would be appreciated).

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


---

## 1 answers

### Answer by username_1 on 2013-06-21. Score: 9 | Accepted answer

The textbook of [Computational Complexity: Modern Approach](http://www.math.sc.edu/~cooper/math778C/abct.pdf), by Arora and Barak gives such example:

They define the decision problem Integer Factoring on input of three positive integers,

$\text{Integer Factoring} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$.

They state that Alon and Kilian showed that if integer $p$ is not required to be prime number then the problem becomes $NP$-complete.

> **Comments:**
> **username_2**: http://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring  
> **username_0**: p.39 in other words "Given three numbers N, L, U decide if N has a prime factor p in the interval [L, U]. The certiﬁcate is the factor p." on p.58 it is stated the NP complete case is an unpublished result from personal communication. does anyone know if its ever been published?  
> **username_1**: @username_0 I don't believe that the proof has been published before. Personaly, I searched a lot for it with no luck.  
> **username_1**: @Anush I believe there are no updates  

---

