42
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ No, IIRC it is open if Primes is P-hard. I think the same is true about FACTORING. $\endgroup$
    – Kaveh
    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$
    – Suresh Venkat
    Aug 29, 2011 at 2:59
  • 1
    $\begingroup$ @Suresh: that is a nice question. Could you post it separately? $\endgroup$
    – András Salamon
    Aug 30, 2011 at 17:39
  • 1
    $\begingroup$ Actually it's already been asked for factoring: cstheory.stackexchange.com/questions/5096/… $\endgroup$
    – Suresh Venkat
    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
    Aug 31, 2011 at 0:32

2 Answers 2

Reset to default
40
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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
    Jan 1, 2017 at 12:46
30
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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