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). Although that's a common
misconception, both discrete log and integer factorization are not
believed to be NP-hard problems. Hence the worry that quantum computers
would break these cryptographic methods despite the face that very few
people believe that they'd be able to solve NP-complete problems in
polynomial time.
Post a reply to this message
|