{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T04:10:46Z","timestamp":1745554246462},"reference-count":23,"publisher":"EDP Sciences","issue":"3","license":[{"start":{"date-parts":[[2013,7,30]],"date-time":"2013-07-30T00:00:00Z","timestamp":1375142400000},"content-version":"vor","delay-in-days":29,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"accepted":{"date-parts":[[2013,6,12]]},"published-print":{"date-parts":[[2013,7]]},"abstract":"<jats:p>We discuss how much space is sufficient to decide whether a unary given number\n            <jats:italic>n<\/jats:italic> is a prime. We show that\n            <jats:italic>O<\/jats:italic>(log\u2009log\u2009<jats:italic>n<\/jats:italic>) space is sufficient for a deterministic\n          Turing machine, if it is equipped with an additional pebble movable along the input tape,\n          and also for an alternating machine, if the space restriction applies only to its\n          accepting computation subtrees. In other words, the language is a prime is in\n            pebble\u2013DSPACE(log\u2009log\u2009<jats:italic>n<\/jats:italic>) and also in\n            accept\u2013ASPACE(log\u2009log\u2009<jats:italic>n<\/jats:italic>). Moreover, if the given\n            <jats:italic>n<\/jats:italic> is composite, such machines are able to find a divisor of\n            <jats:italic>n<\/jats:italic>. Since <jats:italic>O<\/jats:italic>(log\u2009log\u2009<jats:italic>n<\/jats:italic>) space is too\n          small to write down a divisor, which might require\n            <jats:italic>\u03a9<\/jats:italic>(log\u2009<jats:italic>n<\/jats:italic>) bits, the witness divisor is indicated by the\n          input head position at the moment when the machine halts.<\/jats:p>","DOI":"10.1051\/ita\/2013038","type":"journal-article","created":{"date-parts":[[2013,7,30]],"date-time":"2013-07-30T14:06:43Z","timestamp":1375193203000},"page":"241-259","source":"Crossref","is-referenced-by-count":2,"title":["Factoring and testing primes in small space"],"prefix":"10.1051","volume":"47","author":[{"given":"Viliam","family":"Geffert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dana","family":"Pardubsk\u00e1","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2013,7,30]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"781","DOI":"10.4007\/annals.2004.160.781","volume":"160","author":"Agrawal","year":"2004","journal-title":"Ann. Math."},{"key":"R2","first-page":"61","volume":"74","author":"Allender","year":"2001","journal-title":"Bull. Eur. Assoc. Theoret. Comput. Sci."},{"key":"R3","unstructured":"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\u201359."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"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\u201318.","DOI":"10.1007\/3-540-60246-1_137"},{"key":"R5","unstructured":"C. Boyer, A History of Mathematics. John Wiley & Sons (1968)."},{"key":"R6","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"Chandra","year":"1981","journal-title":"J. Assoc. Comput. Mach."},{"key":"R7","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0304-3975(86)90112-X","volume":"44","author":"Chang","year":"1986","journal-title":"Theoret. Comput. Sci."},{"key":"R8","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0304-3975(91)90391-E","volume":"80","author":"Chang","year":"1991","journal-title":"Theoret. Comput. Sci."},{"key":"R9","unstructured":"A. Chiu, Complexity of Parallel Arithmetic Using The Chinese Remainder Representation. Master\u2019s thesis, University Wisconsin-Milwaukee (1995). (G. Davida, supervisor)."},{"key":"R10","first-page":"259","volume":"35","author":"Chiu","year":"2001","journal-title":"RAIRO: ITA"},{"key":"R11","doi-asserted-by":"crossref","first-page":"756","DOI":"10.1137\/0220048","volume":"20","author":"Davida","year":"1991","journal-title":"SIAM J. Comput."},{"key":"R12","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0020-0190(94)00021-2","volume":"50","author":"Dietz","year":"1994","journal-title":"Inform. Process. Lett."},{"key":"R13","unstructured":"W. Ellison and F. Ellison, Prime Numbers. John Wiley & Sons (1985)."},{"key":"R14","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1137\/0220031","volume":"20","author":"Geffert","year":"1991","journal-title":"SIAM J. Comput."},{"key":"R15","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1137\/S0097539796301306","volume":"28","author":"Geffert","year":"1999","journal-title":"SIAM J. Comput."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"V. Geffert and D. Pardubsk\u00e1, Unary coded NP-complete languages in ASPACE(log\u2009log\u2009n), in Proc. of Develop. Lang. Theory, Lect. Notes Comput. Sci., vol. 7410. Springer-Verlag (2012) 166\u201377.","DOI":"10.1007\/978-3-642-31653-1_16"},{"key":"R17","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1137\/0222011","volume":"22","author":"Iwama","year":"1993","journal-title":"SIAM J. Comput."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"N. Koblitz, A Course in Number Theory and Cryptography, Graduate Texts in Math., vol. 114. Springer-Verlag (1994).","DOI":"10.1007\/978-1-4419-8592-7"},{"key":"R19","unstructured":"I.\u2009I. 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\u201322."},{"key":"R20","unstructured":"C. Mereghetti, The descriptional power of sublogarithmic resource bounded Turing machines. In Proc. of Descr. Compl. Formal Syst. IFIP (2007) 12\u201326. (To appear in J. Automat. Lang. Combin)."},{"key":"R21","unstructured":"P. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, in Proc. of IEEE Symp. Found. Comput. Sci. (1994) 124\u201334."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"A. Szepietowski, Turing Machines with Sublogarithmic Space, Lect. Notes Comput. Sci., vol. 843. Springer-Verlag (1994).","DOI":"10.1007\/3-540-58355-6"},{"key":"R23","unstructured":"http:\/\/en.wikipedia.org\/[0]wiki\/[0]Primenumbertheorem."}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2013038\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,3]],"date-time":"2021-09-03T11:53:57Z","timestamp":1630670037000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2013038"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7]]},"references-count":23,"journal-issue":{"issue":"3"},"alternative-id":["ita110040"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2013038","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,7]]}}}