Key length security (calculations!)

[hughes@ah.com (Eric Hughes)]

First Tim wrote:
   > Factoring is suspected to be in the class NP (or
   > even harder, some suspect), but it has not yet been proved to be so.

NP is nondeterministic polynomial time, meaning that you can verify
the answer in polynomial time.  You need not be able to derive the
answer in P time.  The 'nondeterministic' part means that the machine
guesses the reason for the correct answer and then verifies that it
has the right answer.  The reasoning is encoded in a piece of data
called a witness.

Since one can multiply two numbers together quickly, factoring is
NP-hard.  (X-hard means that the answer comes from a 'short' sequence
of decision questions in complexity class X.)  The verification,
multiplication, is in P, so factoring, the inverse of multiplication,
is NP-hard.  

Since every P problem can be verified in P time (by running the P time
algorithm without the need for a witness), P is a subset of NP.  The
unknown question is whether it is a proper subset.

Then James wrote:
   Those who have studied the matter generally believe that factoring
   is NP, but is not NP complete.

Factoring isn't in NP.  Factoring is NP-hard.  Problems in P and NP
are decision problems, i.e. problems which have true or false answers.
NP-hard means that the problem can be reduced to answering a short
list of NP problems.  In this case, those questions might be "Is the
second-lowest bit of the smallest factor a 1?" and so on, questions
about specific properties of the factorization.  Note that a
factorization makes a suitable witness for every such NP question.

   Factoring cannot be "even harder than NP" since a simple minded
   brute force attack is 2^(n/2), which is only NP

2^n problems give you E, exponential time.  There's also NE,
nondetermistic exponential time, problems which have witnesses
verifiable in E time.  Merely having an exponential time algorithm
does not mean that the problem is in NP.

NP is a subset of E, however.  The easy algorithm is exhaustive search
of the space of possible witnesses, which in exponential in the length
of the P time verification method, and therefore exponential in the
length of the input.

   As Timothy May points out, if factoring is NP, then modest increases
   in key length can easily defeat enormous improvements in factoring.

Also not quite true.  Consider a putative problem whose provably best
algorithm is O(n^(log log n)).  This algorithm dominates every
polynomial (and hence is _not_ in P), but grows extremely slowly.  How
extremely?  Take the log base at 10 and n = 1 googol.  The calculation
yields O(n^2).  No such algorithms or problems are known, I might add;
neither is their existence firmly denied.

Eric