Self-witnessing polynomial-time complexity and prime factorization
Michael R. Fellows, Neal Koblitz · 2003
For a number of computational search, problems, the existence of a polynomial-time algorithm for the problem implies that such an algorithm for the problem is constructively known. Some instances of such self-witnessing polynomial-time complexity are presented. The main result demonstrates this property for the problem of computing the prime factorization of a positive integer, based on a lemma which shows that a certificate for primality or compositeness can be constructed for a positive integer p in deterministic polynomial time given a complete factorization of p-1. A consequence is that primality testing is unconditionally in the intersection of UP and coUP.>