Geodesic
Factoring and testing primes in small space
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) no. 3, pp. 241-259

Voir la notice de l'article provenant de la source Numdam

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.

DOI : 10.1051/ita/2013038
Classification : 11A51, 68Q15, 68Q17
Keywords: prime numbers, factoring, sublogarithmic space, computational complexity 
@article{ITA_2013__47_3_241_0,
     author = {Geffert, Viliam and Pardubsk\'a, Dana},
     title = {Factoring and testing primes in small space},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {241--259},
     publisher = {EDP-Sciences},
     volume = {47},
     number = {3},
     year = {2013},
     doi = {10.1051/ita/2013038},
     mrnumber = {3103127},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2013038/}
}
TY  - JOUR
AU  - Geffert, Viliam
AU  - Pardubská, Dana
TI  - Factoring and testing primes in small space
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2013
SP  - 241
EP  - 259
VL  - 47
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2013038/
DO  - 10.1051/ita/2013038
LA  - en
ID  - ITA_2013__47_3_241_0
ER  - 
%0 Journal Article
%A Geffert, Viliam
%A Pardubská, Dana
%T Factoring and testing primes in small space
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2013
%P 241-259
%V 47
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2013038/
%R 10.1051/ita/2013038
%G en
%F ITA_2013__47_3_241_0
Geffert, Viliam; Pardubská, Dana. Factoring and testing primes in small space. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) no. 3, pp. 241-259. doi: 10.1051/ita/2013038

Cité par Sources :