Factoring and testing primes in small space
Geffert, Viliam ; Pardubská, Dana
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013), p. 241-259 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2013-01-01
DOI : https://doi.org/10.1051/ita/2013038
Classification:  11A51,  68Q15,  68Q17 
@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},
     volume = {47},
     year = {2013},
     pages = {241-259},
     doi = {10.1051/ita/2013038},
     mrnumber = {3103127},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 241-259. doi : 10.1051/ita/2013038. http://gdmltest.u-ga.fr/item/ITA_2013__47_3_241_0/

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

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

[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 1467265 | Zbl 1193.68119

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

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

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

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

[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 1869217 | Zbl 1014.68062

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

[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 1281051 | Zbl 0807.68051

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

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

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

[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. | Zbl pre06101636

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

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

[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 0907.68081

[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 1489242

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

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