Factoring - State of the Art and Predictions

James A. Donald jamesd at netcom.com
Sun Feb 12 17:13:08 PST 1995

On Sun, 12 Feb 1995, Jonathan Rochkind wrote:
> Keep in mind that it's been mathematically proven that factoring is
> NP-complete.  That is, it's in the set of problems including such things as
> discrete logs and the travelling salesman problem, such that if a
> polynomial time solution is found to _any_ of these problems, one can be
> found for all of them. i

This is news to me!

I am fairly sure that factoring and discrete log are *not*
NP complete, and indeed there is no known way to use
NP complete problems for crypto.

We have the right to defend ourselves     |   http://www.catalog.com/jamesd/
and our property, because of the kind     |  
of animals that we are. True law          |   James A. Donald
derives from this right, not from the     |  
arbitrary power of the omnipotent state.  |   jamesd at netcom.com

More information about the cypherpunks-legacy mailing list