|
![](/i/fill.gif) |
Kevin Wampler wrote:
> Darren New wrote:
>> Kevin Wampler wrote:
>>> commonly used encryption algorithms which are believed to be NP-hard to
>>
>> Diffie Hellman is based on discrete log. Isn't that NP?
>>
>
> Yes, although not in the way that you mean. It's trivially shown to be
> in NP in the sense that many things are in NP which are not NP-hard (for
> instance anything in P is also in NP).
Well, obviously that's what I meant. I just wasn't being pedantic.
> Although that's a common
> misconception, both discrete log and integer factorization are not
> believed to be NP-hard problems.
OK. That's what I wasn't sure of. I thought discrete log was proven NP-hard.
So, no, I don't know of any crypto algorithms that depend on p!=np.
--
Darren New, San Diego CA, USA (PST)
C# - a language whose greatest drawback
is that its best implementation comes
from a company that doesn't hate Microsoft.
Post a reply to this message
|
![](/i/fill.gif) |