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?

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

2 Answers 2


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.

  • $\begingroup$ 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? $\endgroup$
    – Turbo
    Commented Jan 1, 2017 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.