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

Abstract

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

How to cite

top

Geffert, 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. [1] M. Agrawal, N. Kayal and N. Saxena, Primes is in P. Ann. Math.160 (2004) 781–93. Zbl1071.11070MR2123939
  2. [2] E. Allender, The division breakthroughs. Bull. Eur. Assoc. Theoret. Comput. Sci.74 (2001) 61–77. Zbl1027.68606MR1858864
  3. [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. [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. [5] C. Boyer, A History of Mathematics. John Wiley & Sons (1968). Zbl0698.01001MR234791
  6. [6] A. K. Chandra, D. C. Kozen and L. J. Stockmeyer. Alternation. J. Assoc. Comput. Mach.28 (1981) 114–33. Zbl0473.68043MR603186
  7. [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. [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. [9] A. Chiu, Complexity of Parallel Arithmetic Using The Chinese Remainder Representation. Master’s thesis, University Wisconsin-Milwaukee (1995). (G. Davida, supervisor). 
  10. [10] A. Chiu, G. Davida and B. Litow, Division in logspace-uniform NC1. RAIRO: ITA 35 (2001) 259–75. Zbl1014.68062MR1869217
  11. [11] G.I. Davida and B. Litow, Fast parallel arithmetic via modular representation. SIAM J. Comput.20 (1991) 756–65. Zbl0736.68040MR1105936
  12. [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. [13] W. Ellison and F. Ellison, Prime Numbers. John Wiley & Sons (1985). Zbl0624.10001MR814687
  14. [14] V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Comput.20 (1991) 484–98. Zbl0762.68022MR1094527
  15. [15] V. Geffert, C. Mereghetti and G. Pighizzini, Sublogarithmic bounds on space and reversals. SIAM J. Comput.28 (1999) 325–40. Zbl0914.68068MR1630493
  16. [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. [17] K. Iwama, ASPACE(o(log log n)) is regular. SIAM J. Comput.22 (1993) 136–46. Zbl0767.68039
  18. [18] N. Koblitz, A Course in Number Theory and Cryptography, Graduate Texts in Math., vol. 114. Springer-Verlag (1994). Zbl0819.11001
  19. [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. [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. [21] P. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, in Proc. of IEEE Symp. Found. Comput. Sci. (1994) 124–34. MR1489242
  22. [22] A. Szepietowski, Turing Machines with Sublogarithmic Space, Lect. Notes Comput. Sci., vol. 843. Springer-Verlag (1994). Zbl0998.68062MR1314820
  23. [23] http://en.wikipedia.org/[0]wiki/[0]Primenumbertheorem. 

NotesEmbed ?

top

You must be logged in to post comments.