Factoring and Testing Primes in Small Space
From MaRDI portal
Publication:3599080
DOI10.1007/978-3-540-95891-8_28zbMath1206.68144OpenAlexW1838335054MaRDI QIDQ3599080
Dana Pardubská, Viliam Geffert
Publication date: 3 February 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: http://www.numdam.org/item?id=ITA_2013__47_3_241_0/
Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Primes (11A41)
Cites Work
- On pebble automata
- Space bounded computations: Review and new separation results
- Bits and relative order from residues, space efficiently
- Turing machines with sublogarithmic space
- PRIMES is in P
- Division in logspace-uniformNC1
- Strong optimal lower bounds for Turing machines that accept nonregular languages
- Alternation
- Fast Parallel Arithmetic via Modular Representation
- Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
- ${\text{ASPACE}}(o(\log \log n))$ is Regular
- Space-Efficient Deterministic Simulation of Probabilistic Automata
- Unnamed Item
- Unnamed Item
- Unnamed Item