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

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$
    – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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