Factoring and Testing Primes in Small Space

DOI10.1007/978-3-540-95891-8_28MaRDI QIDQ3599080zbMATH OpenOpenAlexFDO

Authors Viliam Geffert, Dana Pardubská

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/

zbMATH Keywords

computational complexityfactoringprime numberssublogarithmic space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Primes (11A41)

Recommendations

• Factoring and testing primes in small space
• Decision problem \texttt{PRIMES}
• A space-efficient fast prime number sieve
• Every Prime Has a Succinct Certificate
• scientific article; zbMATH DE number 1186941

Cites work

• scientific article; zbMATH DE number 4012703 (Why is no real title available?)
• scientific article; zbMATH DE number 682387 (Why is no real title available?)
• ${\text{ASPACE}}(o(\log \log n))$ is Regular
• Alternation
• Bits and relative order from residues, space efficiently
• Division in logspace-uniform NC
• Fast Parallel Arithmetic via Modular Representation
• Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
• On pebble automata
• PRIMES is in P
• Space bounded computations: Review and new separation results
• Space-Efficient Deterministic Simulation of Probabilistic Automata
• Strong optimal lower bounds for Turing machines that accept nonregular languages
• The division breakthroughs
• Turing machines with sublogarithmic space

Cited in

(2)

• Factoring and testing primes in small space
• A space-efficient fast prime number sieve

This page was built for publication: Factoring and Testing Primes in Small Space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3599080)