<p>PRIMES is known to be hard for $\mathsf{TC^0}$.  See my paper with Saks and Shparlinski, "<a href="http://ftp.cs.rutgers.edu/pub/allender/primes.pdf">A Lower Bound for Primality</a>" in JCSS 62 (2001).  No improvement on that front since then.</p>

CC BY-SA 3.0
2017-01-01T12:46:35.133Z
do you know if this hardness result also holds if we only want some random $\frac1 n$ of all $n$-bit integers to be factored? After all this could still be in $ACC^0$ right?
Turbo
CC BY-SA 3.0
2011-08-30T17:52:32.067Z
2014-02-18T12:30:18.970Z
2014-02-18T12:30:18.970Z
Eric Allender
<p>Factoring can be achieved by using a polylog $n$ depth quantum circuit, and ZPP pre- and post-processing; <a href="http://arxiv.org/abs/quant-ph/0006004">see this paper</a>. If it were P-hard, any algorithm in P could be done with polylog $n$ depth quantum circuit and the same pre- and post-processing steps. I believe these steps are modular exponentiation and continued fractions, which to me seem unlikely to be powerful enough to solve P-complete problems, even with the addition of a polylog $n$ depth quantum circuit.</p>

CC BY-SA 3.0
2011-08-31T01:16:07.420Z
2011-08-31T01:16:07.420Z
Peter Shor 
<p>Let <a href="http://en.wikipedia.org/wiki/Primality_test">PRIMES</a> (a.k.a. <em>primality testing</em>) be the problem: </p>

<blockquote>
  <p>Given a natural number $n$, is $n$ a prime number?</p>
</blockquote>

<p>Let <a href="http://en.wikipedia.org/wiki/Integer_factorization">FACTORING</a> be the problem: </p>

<blockquote>
  <p>Given natural numbers $n$, $m$ with $1 \leq m \leq n$, does $n$ have a factor $d$ with $1 &lt; d &lt; m$?</p>
</blockquote>

<p>Is it known whether PRIMES is P-hard? How about FACTORING? 
What are the best known lowerbounds for these problems?</p>

CC BY-SA 3.0
2011-08-29T01:42:05.820Z
No, IIRC it is open if Primes is P-hard. I think the same is true about FACTORING.
Kaveh
CC BY-SA 3.0
2011-08-29T02:59:12.053Z
I guess an alternate question might be: are there any consequences for PRIMES or FACTORING being P-hard ?
Suresh Venkat
CC BY-SA 3.0
2011-08-30T17:39:03.460Z
@Suresh: that is a nice question.  Could you post it separately?
András Salamon
CC BY-SA 3.0
2011-08-30T19:36:39.923Z
Actually it's already been asked for factoring: http://cstheory.stackexchange.com/questions/5096/consequences-of-factoring-being-in-p
Suresh Venkat
CC BY-SA 3.0
2011-08-30T20:30:32.070Z
@András I would suggested that the consequences be assumed (or explicitly added) as part of this question. Otherwise the question starts to border on wikipedia-able.
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-31T00:32:45.977Z
@Artem, I agree with András, a question about consequences of P-hardness of Primes would be interesting. I also edited the question by adding a question about the best known lowerbounds.
Kaveh
CC BY-SA 3.0
2011-08-31T01:54:15.673Z
@Suresh, that seems to be about the consequences of upperbound for FACTORING (being in P), not a lowerbound for it (being P-hard).
Kaveh
CC BY-SA 3.0
2011-08-31T03:37:41.070Z
@Kaveh Hmm. good point. although Peter Shor appears to have answered the question for FACTORING
Suresh Venkat
CC BY-SA 3.0
2011-08-31T14:11:00.003Z
What type of reduction are we considering?
Tyson Williams
<cc.complexity-theory><lower-bounds><factoring><primes><p-hardness>
Are the problems PRIMES, FACTORING known to be P-hard?
k m
# Are the problems PRIMES, FACTORING known to be P-hard?

(Asked by: username_0 on 2011-08-29)

Let [PRIMES](http://en.wikipedia.org/wiki/Primality_test) (a.k.a. *primality testing*) be the problem:

> Given a natural number $n$, is $n$ a prime number?

Let [FACTORING](http://en.wikipedia.org/wiki/Integer_factorization) be the problem:

> Given natural numbers $n$, $m$ with $1 \leq m \leq n$, does $n$ have a factor $d$ with $1 < d < m$?

Is it known whether PRIMES is P-hard? How about FACTORING?
What are the best known lowerbounds for these problems?

**Tags:** cc.complexity-theory, lower-bounds, factoring, primes, p-hardness
> **Comments:**
> **username_1**: No, IIRC it is open if Primes is P-hard. I think the same is true about FACTORING.  
> **username_2**: I guess an alternate question might be: are there any consequences for PRIMES or FACTORING being P-hard ?  
> **username_3**: @Suresh: that is a nice question.  Could you post it separately?  
> **username_2**: Actually it's already been asked for factoring: http://cstheory.stackexchange.com/questions/5096/consequences-of-factoring-being-in-p  
> **username_4**: @András I would suggested that the consequences be assumed (or explicitly added) as part of this question. Otherwise the question starts to border on wikipedia-able.  
> **username_1**: @Artem, I agree with András, a question about consequences of P-hardness of Primes would be interesting. I also edited the question by adding a question about the best known lowerbounds.  
> **username_1**: @Suresh, that seems to be about the consequences of upperbound for FACTORING (being in P), not a lowerbound for it (being P-hard).  
> **username_2**: @Kaveh Hmm. good point. although Peter Shor appears to have answered the question for FACTORING  
> **username_5**: What type of reduction are we considering?  

---

## 2 answers

### Answer by username_6 on 2011-08-30. Score: 41

PRIMES is known to be hard for $\mathsf{TC^0}$. See my paper with Saks and Shparlinski, "[A Lower Bound for Primality](http://ftp.cs.rutgers.edu/pub/allender/primes.pdf)" in JCSS 62 (2001). No improvement on that front since then.

> **Comments:**
> **username_7**: do you know if this hardness result also holds if we only want some random $\frac1 n$ of all $n$-bit integers to be factored? After all this could still be in $ACC^0$ right?  

---

### Answer by username_8 on 2011-08-31. Score: 32

Factoring can be achieved by using a polylog $n$ depth quantum circuit, and ZPP pre- and post-processing; [see this paper](http://arxiv.org/abs/quant-ph/0006004). If it were P-hard, any algorithm in P could be done with polylog $n$ depth quantum circuit and the same pre- and post-processing steps. I believe these steps are modular exponentiation and continued fractions, which to me seem unlikely to be powerful enough to solve P-complete problems, even with the addition of a polylog $n$ depth quantum circuit.


---

