1995-02-13 - Re: Factoring - State of the Art and Predictions

Header Data

From: Matt Blaze <mab@crypto.com>
To: jrochkin@cs.oberlin.edu (Jonathan Rochkind)
Message Hash: 0f4d3a27383ec806032d087b5097862c11781d4609b4042cbde9300113a0f609
Message ID: <199502130119.UAA03807@crypto.com>
Reply To: <ab645cdf0102100421a7@[132.162.201.201]>
UTC Datetime: 1995-02-13 01:17:01 UTC
Raw Date: Sun, 12 Feb 95 17:17:01 PST

Raw message

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





Thread