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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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
Also note that logspace is in P (there are only polynomial state configurations with logspace), so factorization in logspace would imply factorization in P.