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.

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
Mots-clés : 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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ita/2013038/

[1] M. Agrawal, N. Kayal and N. Saxena, Primes is in P. Ann. Math. 160 (2004) 781-93. | MR | Zbl

[2] E. Allender, The division breakthroughs. Bull. Eur. Assoc. Theoret. Comput. Sci. 74 (2001) 61-77. | MR | Zbl

[3] E. Allender, D.A. Mix Barrington and W. Hesse, Uniform circuits for division: Consequences and problems, in Proc. of IEEE Conf. Comput. Complexity (2001) 150-59.

[4] A. Bertoni, C. Mereghetti and G. Pighizzini, Strong optimal lower bounds for Turing machines that accept nonregular languages, in Proc. of Math. Found. Comput. Sci., Lect. Notes Comput. Sci., vol. 969. Springer-Verlag (1995) 309-18. | MR | Zbl

[5] C. Boyer, A History of Mathematics. John Wiley & Sons (1968). | MR | Zbl

[6] A. K. Chandra, D. C. Kozen and L. J. Stockmeyer. Alternation. J. Assoc. Comput. Mach. 28 (1981) 114-33. | MR | Zbl

[7] J.H. Chang, O. H. Ibarra, M.A. Palis and B. Ravikumar, On pebble automata. Theoret. Comput. Sci. 44 (1986) 111-21. | MR | Zbl

[8] R. Chang, J. Hartmanis and D. Ranjan. Space bounded computations: Review and new separation results. Theoret. Comput. Sci. 80 (1991) 289-302. | MR | Zbl

[9] A. Chiu, Complexity of Parallel Arithmetic Using The Chinese Remainder Representation. Master's thesis, University Wisconsin-Milwaukee (1995). (G. Davida, supervisor).

[10] A. Chiu, G. Davida and B. Litow, Division in logspace-uniform NC1. RAIRO: ITA 35 (2001) 259-75. | Numdam | MR | Zbl

[11] G.I. Davida and B. Litow, Fast parallel arithmetic via modular representation. SIAM J. Comput. 20 (1991) 756-65. | MR | Zbl

[12] P.F. Dietz, I.I. Macarie and J.I. Seiferas, Bits and relative order from residues, space efficiently. Inform. Process. Lett. 50 (1994) 123-27. | MR | Zbl

[13] W. Ellison and F. Ellison, Prime Numbers. John Wiley & Sons (1985). | MR | Zbl

[14] V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Comput. 20 (1991) 484-98. | MR | Zbl

[15] V. Geffert, C. Mereghetti and G. Pighizzini, Sublogarithmic bounds on space and reversals. SIAM J. Comput. 28 (1999) 325-40. | MR | Zbl

[16] V. Geffert and D. Pardubská, Unary coded NP-complete languages in ASPACE(log log n), in Proc. of Develop. Lang. Theory, Lect. Notes Comput. Sci., vol. 7410. Springer-Verlag (2012) 166-77.

[17] K. Iwama, ASPACE(o(log log n)) is regular. SIAM J. Comput. 22 (1993) 136-46. | Zbl

[18] N. Koblitz, A Course in Number Theory and Cryptography, Graduate Texts in Math., vol. 114. Springer-Verlag (1994). | Zbl

[19] I. I. Macarie, Space-efficient deterministic simulation of probabilistic automata, in Proc. of Symp. Theoret. Aspects Comput. Sci., Lect. Notes Comput. Sci., vol. 775. Springer-Verlag (1994) 109-22. | Zbl

[20] C. Mereghetti, The descriptional power of sublogarithmic resource bounded Turing machines. In Proc. of Descr. Compl. Formal Syst. IFIP (2007) 12-26. (To appear in J. Automat. Lang. Combin).

[21] P. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, in Proc. of IEEE Symp. Found. Comput. Sci. (1994) 124-34. | MR

[22] A. Szepietowski, Turing Machines with Sublogarithmic Space, Lect. Notes Comput. Sci., vol. 843. Springer-Verlag (1994). | MR | Zbl

[23] http://en.wikipedia.org/[0]wiki/[0]Primenumbertheorem.

Cité par Sources :