# Factoring and testing primes in small space

Viliam Geffert; Dana Pardubská

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2013)

- Volume: 47, Issue: 3, page 241-259
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topGeffert, Viliam, and Pardubská, Dana. "Factoring and testing primes in small space." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 47.3 (2013): 241-259. <http://eudml.org/doc/273058>.

@article{Geffert2013,

abstract = {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.},

author = {Geffert, Viliam, Pardubská, Dana},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {prime numbers; factoring; sublogarithmic space; computational complexity},

language = {eng},

number = {3},

pages = {241-259},

publisher = {EDP-Sciences},

title = {Factoring and testing primes in small space},

url = {http://eudml.org/doc/273058},

volume = {47},

year = {2013},

}

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

PB - EDP-Sciences

VL - 47

IS - 3

SP - 241

EP - 259

AB - 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.

LA - eng

KW - prime numbers; factoring; sublogarithmic space; computational complexity

UR - http://eudml.org/doc/273058

ER -

## References

top- [1] M. Agrawal, N. Kayal and N. Saxena, Primes is in P. Ann. Math.160 (2004) 781–93. Zbl1071.11070MR2123939
- [2] E. Allender, The division breakthroughs. Bull. Eur. Assoc. Theoret. Comput. Sci.74 (2001) 61–77. Zbl1027.68606MR1858864
- [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. Zbl1193.68119MR1467265
- [5] C. Boyer, A History of Mathematics. John Wiley & Sons (1968). Zbl0698.01001MR234791
- [6] A. K. Chandra, D. C. Kozen and L. J. Stockmeyer. Alternation. J. Assoc. Comput. Mach.28 (1981) 114–33. Zbl0473.68043MR603186
- [7] J.H. Chang, O. H. Ibarra, M.A. Palis and B. Ravikumar, On pebble automata. Theoret. Comput. Sci.44 (1986) 111–21. Zbl0612.68045MR858693
- [8] R. Chang, J. Hartmanis and D. Ranjan. Space bounded computations: Review and new separation results. Theoret. Comput. Sci.80 (1991) 289–302. Zbl0745.68051MR1117067
- [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. Zbl1014.68062MR1869217
- [11] G.I. Davida and B. Litow, Fast parallel arithmetic via modular representation. SIAM J. Comput.20 (1991) 756–65. Zbl0736.68040MR1105936
- [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. Zbl0807.68051MR1281051
- [13] W. Ellison and F. Ellison, Prime Numbers. John Wiley & Sons (1985). Zbl0624.10001MR814687
- [14] V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Comput.20 (1991) 484–98. Zbl0762.68022MR1094527
- [15] V. Geffert, C. Mereghetti and G. Pighizzini, Sublogarithmic bounds on space and reversals. SIAM J. Comput.28 (1999) 325–40. Zbl0914.68068MR1630493
- [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. Zbl1316.68062
- [17] K. Iwama, ASPACE(o(log log n)) is regular. SIAM J. Comput.22 (1993) 136–46. Zbl0767.68039
- [18] N. Koblitz, A Course in Number Theory and Cryptography, Graduate Texts in Math., vol. 114. Springer-Verlag (1994). Zbl0819.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. Zbl0907.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. MR1489242
- [22] A. Szepietowski, Turing Machines with Sublogarithmic Space, Lect. Notes Comput. Sci., vol. 843. Springer-Verlag (1994). Zbl0998.68062MR1314820
- [23] http://en.wikipedia.org/[0]wiki/[0]Primenumbertheorem.