From: Matt Blaze <mab@crypto.com>
Date: Sun, 12 Feb 95 17:17:01 PST
To: jrochkin@cs.oberlin.edu (Jonathan Rochkind)
Subject: Re: Factoring - State of the Art and Predictions
In-Reply-To: <ab645cdf0102100421a7@[132.162.201.201]>
Message-ID: <199502130119.UAA03807@crypto.com>
MIME-Version: 1.0
Content-Type: text/plain



Johnathan Rochkind writes:
>
>Keep in mind that it's been mathematically proven that factoring is
>NP-complete.
...

No it hasn't.  Factoring is believed to be hard, but no one has ever
shown it to be NP-hard (let alone NP complete).

...
>factoring.   Logarithms, for instance, are used in some crypto systems, and
>are another suspected Hard Problem, but are also NP complete.  So if
>factoring is solved,  discrete logarithms will be solved too.

Ditto for discrete log.

-matt