| Issue |
RAIRO-Theor. Inf. Appl.
Volume 47, Number 3, July-August 2013
|
|
|---|---|---|
| Page(s) | 241 - 259 | |
| Section | Articles | |
| DOI | https://doi.org/10.1051/ita/2013038 | |
| Published online | 30 July 2013 | |
Factoring and testing primes in small space∗
1 Department of Computer Science, P. J.
Šafárik University, Jesenná 5, 04001
Košice,
Slovakia.
viliam.geffert@upjs.sk
2 Department of Computer Science,
Comenius University, Mlynská dolina, 84248
Bratislava,
Slovakia.
pardubska@dcs.fmph.uniba.sk
Received:
3
December
2011
Accepted:
12
June
2013
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 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 Ω(log n) bits, the witness divisor is indicated by the input head position at the moment when the machine halts.
Mathematics Subject Classification: 11A51 / 68Q15 / 68Q17
Key words: Prime numbers / factoring / sublogarithmic space / computational complexity
The first author was supported under contract VEGA 1/0479/12 “Combinatorial Structures and Complexity of Algorithms”, the second author partially supported under contract VEGA 1/0671/11 “Computations with Supplementary Information”. A preliminary version of this work was presented at SOFSEM 2009 [Lect. Notes Comput. Sci., vol. 5404. Springer-Verlag (2009) 291–302].
© EDP Sciences 2013
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.