From: djimenez@bluebonnet.uthscsa.edu (Daniel Jimenez) Newsgroups: sci.math Subject: Re: Number-theoretic implications of P=NP? Date: 15 Apr 1998 20:11:23 GMT In article <6h1bkc$9d4@netra.montana.edu>, Louis Glassy wrote: >If it were proven that P=NP, would this have any >implications for factoring? Would the general >factoring problem become any easier to solve? Yes, P=NP implies that there is a polynomial time algorithm for factoring, so factoring would become asymptotically easier (but not necessarily easier in practice for the numbers people really want to factor). >I have some research I'm working on that involves >factoring large numbers, and I'm curious if >a solution to this P=NP problem would have any >practical benefits for factoring. I've read a >number of CS and computational complexity theory >texts, but none of them seem to provide more than: > >[1] factoring is really hard, maybe not in NP. Factoring is in NP. NP is the class of decision problems with polynomial time proof systems. A decision problem related to factoring is this: Instance: Two integers, n and m Question: Is there a nontrivial factor of n less than m? This problem is in NP since, if the answer is "yes" then a poly-time verifiable certificate (a nontrivial factor) exists. (Finding the certificate is the the problem.) With an algorithm capable of answering that question in time t(n), you can either ask it for the certificate or do a binary search for a factor in time O(t(n) log n). If P=NP, then there exists an algorithm capable of answering that question in time t(n) = O(log^k n) for some constant k (i.e., time polynomial in the size of n), so factoring would take O(log^(k+1) n). Of course, that doesn't mean the smallest possible k isn't 100 or something, so factoring could still be hard in a practical sense. >[2] prime testing with absolute certainty > is really hard, probably in coNP. Primality testing is both in NP and co-NP. It's also in P, if the Generalized Riemann Hypothesis is true. >Any insights would be appreciated. In an amazing coincidence, yesterday I taught my Analysis of Algorithms class about P and NP using using factoring as an example of a problem in NP. If you'd like to see the lecture notes, they are at http://www.cs.utsa.edu/~djimenez/cs3343/lecture22.html . -- Daniel Jiménez djimenez@bluebonnet.uthscsa.edu "I've so much music in my head" -- Maurice Ravel, shortly before his death. " " -- John Cage