[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Factoring - State of the Art and Predictions


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