Geffert, Viliam; Pardubská, Dana Factoring and testing primes in small space. (English) Zbl 1315.11100 RAIRO, Theor. Inform. Appl. 47, No. 3, 241-259 (2013). Summary: We discuss how much space is sufficient to decide whether a unary given number \(n\) is a prime. We show that \(O(\log\log n)\) space is sufficient for a deterministic Turing machine, if it is equipped with an additional pebble movable along the input tape, and also for an alternating machine, if the space restriction applies only to its accepting computation subtrees. In other words, the language \(\mathrm{un-Primes} =\{1^n: n\text{ is a prime}\}\) is in pebble-DSPACE\((\log\log n)\) and also in accept-ASPACE\((\log\log n)\). Moreover, if the given \(n\) is composite, such machines are able to find a divisor of \(n\). Since \(O(\log\log n)\) space is too small to write down a divisor, which might require \(\Omega(\log n)\) bits, the witness divisor is indicated by the input head position at the moment when the machine halts.A preliminary version appeared in [SOFSEM 2009, Lect. Notes Comput. Sci. 5404, 291–302 (2009; Zbl 1206.68144)]. Cited in 1 Document MSC: 11Y16 Number-theoretic algorithms; complexity 11A51 Factorization; primality 68Q05 Models of computation (Turing machines, etc.) (MSC2010) 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) Keywords:prime numbers; factoring; sublogarithmic space; computational complexity Citations:Zbl 1206.68144 PDFBibTeX XMLCite \textit{V. Geffert} and \textit{D. Pardubská}, RAIRO, Theor. Inform. Appl. 47, No. 3, 241--259 (2013; Zbl 1315.11100) Full Text: DOI Link