42

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?

Kaveh
  • 21,577
  • 8
  • 82
  • 183
k m
  • 421
  • 3
  • 3
  • 2
    No, IIRC it is open if Primes is P-hard. I think the same is true about FACTORING. – Kaveh Aug 29 '11 at 01:42
  • 11
    I guess an alternate question might be: are there any consequences for PRIMES or FACTORING being P-hard ? – Suresh Venkat Aug 29 '11 at 02:59
  • 1
    @Suresh: that is a nice question. Could you post it separately? – András Salamon Aug 30 '11 at 17:39
  • 1
    Actually it's already been asked for factoring: http://cstheory.stackexchange.com/questions/5096/consequences-of-factoring-being-in-p – Suresh Venkat Aug 30 '11 at 19:36
  • @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 Aug 30 '11 at 20:30
  • 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. – Kaveh Aug 31 '11 at 00:32
  • @Suresh, that seems to be about the consequences of upperbound for FACTORING (being in P), not a lowerbound for it (being P-hard). – Kaveh Aug 31 '11 at 01:54
  • @Kaveh Hmm. good point. although Peter Shor appears to have answered the question for FACTORING – Suresh Venkat Aug 31 '11 at 03:37
  • What type of reduction are we considering? – Tyson Williams Aug 31 '11 at 14:11

2 Answers2

40

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.

dd1
  • 537
  • 5
  • 10
Eric Allender
  • 1,871
  • 21
  • 16
  • 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 Jan 01 '17 at 12:46
31

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.

Peter Shor
  • 24,763
  • 4
  • 93
  • 133