On Mon, May 18, 2009, Kyle Hamilton wrote: > > Both of which are described as "hard problems". It's not known > whether they qualify as NP-complete, but they definitely qualify as > NP-hard (NP meaning 'nonpolynomial time', or 'the amount of time > required to do it is logarithmic with how much information needs to be > processed', which is why larger key sizes are typically better). >
After all these years something in my PhD thesis has come up! Actually NP is nondeterministic polynomial time. This is *not* the same as saying not polynomial time. That is suspected to be the case but proving it would be equivalent to solving the unsolved P!=NP problem. It is strongly suspected integer factorization (for RSA) is not NP-complete That isn't to say it is thought to be in P... several classes of intractable problem exist that are harder than NP-complete. It is in fact trivial to show that integer factorisation is in NP so it isn't NP-hard. Wikipedia has a number of interesting articles on these topics... Steve. -- Dr Stephen N. Henson. Email, S/MIME and PGP keys: see homepage OpenSSL project core developer and freelance consultant. Homepage: http://www.drh-consultancy.demon.co.uk ______________________________________________________________________ OpenSSL Project http://www.openssl.org User Support Mailing List openssl-users@openssl.org Automated List Manager majord...@openssl.org
