Factoring and Testing Primes in Small Space

DOI10.1007/978-3-540-95891-8_28zbMATH Open1206.68144OpenAlexW1838335054MaRDI QIDQ3599080FDOQ3599080

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/

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 Keywords

computational complexityfactoringprime numberssublogarithmic space

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (1)

• 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)