# Are the problems PRIMES, FACTORING known to be P-hard?

Let PRIMES (a.k.a. primality testing) be the problem:

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

Let FACTORING 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?

• No, IIRC it is open if Primes is P-hard. I think the same is true about FACTORING. Aug 29 '11 at 1:42
• I guess an alternate question might be: are there any consequences for PRIMES or FACTORING being P-hard ? Aug 29 '11 at 2:59
• @Suresh: that is a nice question. Could you post it separately? Aug 30 '11 at 17:39
• Actually it's already been asked for factoring: cstheory.stackexchange.com/questions/5096/… Aug 30 '11 at 19:36
• @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. Aug 31 '11 at 0:32

## 2 Answers

PRIMES is known to be hard for $\mathsf{TC^0}$. See my paper with Saks and Shparlinski, "A Lower Bound for Primality" in JCSS 62 (2001). No improvement on that front since then.

• 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?
– Mr.
Jan 1 '17 at 12:46

Factoring can be achieved by using a polylog $n$ depth quantum circuit, and ZPP pre- and post-processing; see this paper. 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.