Self-witnessing polynomial-time complexity and prime factorization

DOI10.1007/BF00141967zbMath0756.11042WikidataQ57360143 ScholiaQ57360143MaRDI QIDQ1200292

Michael R. Fellows, Neal Koblitz

Publication date: 16 January 1993

Published in: Designs, Codes and Cryptography (Search for Journal in Brave)

zbMATH Keywords

polynomial-time algorithm; prime factorization; planar cover search; time self-witnessing

Mathematics Subject Classification ID

11Y16: Number-theoretic algorithms; complexity

03D15: Complexity of computation (including implicit computational complexity)

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

11Y05: Factorization

Related Items

The Helping Hierarchy, Computing functions with parallel queries to NP, A note on quadratic residuosity and UP, The relative complexity of NP search problems, The counting complexity of group-definable languages, Using partial smoothness of 𝑝-1 for factoring polynomials modulo 𝑝, Proving primality in essentially quartic random time, A deterministic version of Pollard’s $p-1$ algorithm

Cites Work

• A course in constructive algebra
• Riemann's hypothesis and tests for primality
• Graph minors. XIII: The disjoint paths problem
• Every Prime Has a Succinct Certificate
• The NP-completeness column: An ongoing guide
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item