<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On 11 Aug 2010, at 21:59, David Biggins wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><span class="Apple-style-span" style="font-family: Arial, sans-serif; font-size: 15px; ">So if factoring a large number that is the product of two primes, to get back the factors, is a problem that is NP</span></span></blockquote></div><br><div><br></div><div>Factorisation (or its decision equivalent, more precisely) is in NP and co-NP, but it's not known if it's in P. It almost certainly isn't NP-complete, which means that if tomorrow someone were to produce a P algorithm for factorization, it wouldn't say anything about P=NP, unless factorization were proved to be NP-complete, which seems unlikely. </div><div><br></div><div>But this is all slightly incidental, because just because something is in NP doesn't mean it's hard in a practical sense, rather than a theoretical sense. It's perfectly possible to have tractable solutions for practical sized problems in harder complexity classes than P whilst not having tractable solutions for equivalently sized P problems. If you can verify in O(n) but only solve in O(n^100) it's still in P, but is probably very hard in reality; if you can verify in O(n) but solve in O((1+epsilon)^n) for a suitably small n we're in NP, but it may in practical terms be a lot easier to deal with. There are bigger threats to factorization as the basis for security than the (highly unlikely) proof that P=NP, and even if P were to be found to equal NP that wouldn't actually provide P-time algorithms for factorization. Conversely, a very efficient factorization algorithm wouldn't say much about P=NP.</div><div><br></div><div>ian</div><div><br></div></body></html>