3
$\begingroup$

Are the integer factorization and PRIMES known to be in LOGSPACE?

Recently, it has been shown by researchers that PRIMES is in P. But this does not say anything about LOGSPACE since it is not known if LOGSPACE = P.

$\endgroup$
  • $\begingroup$ Factorization definitely isn't, if it were then RSA encryption would be easily broken because factorization would be in P. $\endgroup$ – jmite Aug 1 '14 at 16:40
  • $\begingroup$ jmite: But we don't know whether $\mathrm{FACTORIZATION}$ is in $\mathrm{P}$ or not. $\endgroup$ – Martin Jonáš Aug 1 '14 at 19:23
  • $\begingroup$ Definitely isn't known, sorry, should have clarified. $\endgroup$ – jmite Aug 1 '14 at 21:15
  • $\begingroup$ I guess the only cases that are currently being tackled by algorithms in P are such cases as close primes... $\endgroup$ – user13675 Aug 9 '14 at 20:37
7
$\begingroup$

Factoring is not known to be even in $\mathsf{P}$.

Primality is not known to be in any class conjectured to be smaller than $\mathsf{P}$ (AFAIK).

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ "Factoring is not known to be even in" BPP. $\;$ $\endgroup$ – user12859 Aug 1 '14 at 21:10
  • $\begingroup$ @Ricky, yes, I wanted to use more famous classes used in the question (and before you say, yes, BPP should be more well-known. :) $\endgroup$ – Kaveh Aug 1 '14 at 21:13
0
$\begingroup$

If the number is unary, yes, both are logspace. Sum up the 1's to find the number. Use trial division.

If the number is in binary, then logspace is in terms of the length of binary input. It's unknown.

Note that some semi-prime's smallest factor is approximately the square root of the number, which has O(n) digits.

Also note that logspace is in P (there are only polynomial state configurations with logspace), so factorization in logspace would imply factorization in P.

| cite | improve this answer | |
$\endgroup$

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.