From: “James A. Donald” <jamesd@netcom.com>
To: Jonathan Rochkind <jrochkin@cs.oberlin.edu>
Message Hash: 016486a198190d85d6675792b31d4bc6823491333c10efa99990fb5ebf0a915a
Message ID: <Pine.3.89.9502121727.A20084-0100000@netcom10>
Reply To: <ab645cdf0102100421a7@[132.162.201.201]>
UTC Datetime: 1995-02-13 01:13:08 UTC
Raw Date: Sun, 12 Feb 95 17:13:08 PST
From: "James A. Donald" <jamesd@netcom.com>
Date: Sun, 12 Feb 95 17:13:08 PST
To: Jonathan Rochkind <jrochkin@cs.oberlin.edu>
Subject: Re: Factoring - State of the Art and Predictions
In-Reply-To: <ab645cdf0102100421a7@[132.162.201.201]>
Message-ID: <Pine.3.89.9502121727.A20084-0100000@netcom10>
MIME-Version: 1.0
Content-Type: text/plain
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@netcom.com
Return to February 1995
Return to “Matt Blaze <mab@crypto.com>”