Factoring and testing primes in small space

DOI10.1051/ita/2013038zbMath1315.11100MaRDI QIDQ5397718

Viliam Geffert, Dana Pardubská

Publication date: 24 February 2014

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/b1ba531b0b502e054b1feb9801b44f79eb400e80

zbMATH Keywords

computational complexity; prime numbers; factoring; sublogarithmic space

Mathematics Subject Classification ID

11Y16: Number-theoretic algorithms; complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

11A51: Factorization; primality