::scr tales from the crypto

[Simon Kinahan]

> Nope.  It's not even proven NP-hard; though I don't have a cite, so feel
> free to find a backup.  It is guessed to be NP-complete, but that
> doesn't mean much when there are $bignun of the smartest mathematicians
> working on it in random security agencies, and we don't know whether
> they'll find a better algorithm than ourselves.  I suppose we have to
> trust that centuries of very smart people haven't managed it, so it must
> be okay.

You are right, it is not shown to be in NP-complete, or NP-hard. It is known
to be in NP, and widely believed not to be in P. Apparently it is also
believed not to be NP-complete, because of something I don't understand:

http://www.wikipedia.com/wiki/Integer+factorization

Simon