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