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$
4
  • $\begingroup$ Factorization definitely isn't, if it were then RSA encryption would be easily broken because factorization would be in P. $\endgroup$ Commented Aug 1, 2014 at 16:40
  • $\begingroup$ jmite: But we don't know whether $\mathrm{FACTORIZATION}$ is in $\mathrm{P}$ or not. $\endgroup$ Commented Aug 1, 2014 at 19:23
  • $\begingroup$ Definitely isn't known, sorry, should have clarified. $\endgroup$ Commented Aug 1, 2014 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
    Commented Aug 9, 2014 at 20:37

2 Answers 2

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).

$\endgroup$
2
  • 1
    $\begingroup$ "Factoring is not known to be even in" BPP. $\;$ $\endgroup$
    – user12859
    Commented Aug 1, 2014 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
    Commented Aug 1, 2014 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.

$\endgroup$

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.