Timothy C. May writes
Factoring is suspected to be in the class NP (or even harder, some suspect), but it has not yet been proved to be so.
Those who have studied the matter generally believe that factoring is NP, but is not NP complete. Factoring cannot be "even harder than NP" since a simple minded brute force attack is 2^(n/2), which is only NP As Timothy May points out, if factoring is NP, then modest increases in key length can easily defeat enormous improvements in factoring.
... if P = NP, then fast factoring methods may be found (fast = polynomial in length).
In the highly unlikely event that P = NP then we have also solved, as an almost trivial special case, the problems of true artificial intelligence, artificial consciousness, and artificial perception, and the failure of one particular form of crypto will not be noticed in the midst of such radical changes. -- --------------------------------------------------------------------- We have the right to defend ourselves and our property, because of the kind of animals that we James A. Donald are. True law derives from this right, not from the arbitrary power of the omnipotent state. jamesd@netcom.com