Self-witnessing polynomial-time complexity and prime factorization
From MaRDI portal
Publication:1200292
DOI10.1007/BF00141967zbMath0756.11042OpenAlexW2106380698WikidataQ57360143 ScholiaQ57360143MaRDI QIDQ1200292
Neal Koblitz, Michael R. Fellows
Publication date: 16 January 1993
Published in: Designs, Codes and Cryptography (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00141967
Number-theoretic algorithms; complexity (11Y16) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Factorization (11Y05)
Related Items (14)
Using partial smoothness of 𝑝-1 for factoring polynomials modulo 𝑝 ⋮ A note on quadratic residuosity and UP ⋮ Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\) ⋮ Computational tameness of classical non-causal models ⋮ Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs ⋮ Computational Complexity Studies of Synchronous Boolean Finite Dynamical Systems ⋮ The Helping Hierarchy ⋮ An extension of a result about divisors in a residue class and its application to reducing integer factorization to computing Euler’s totient ⋮ Computing functions with parallel queries to NP ⋮ Solving parity games via priority promotion ⋮ A deterministic version of Pollard’s $p-1$ algorithm ⋮ The relative complexity of NP search problems ⋮ The counting complexity of group-definable languages ⋮ Proving primality in essentially quartic random time
Cites Work
This page was built for publication: Self-witnessing polynomial-time complexity and prime factorization
