From: hughes@ah.com (Eric Hughes)
Date: Sat, 16 Jul 94 10:13:10 PDT
To: cypherpunks@toad.com
Subject: Factoring
In-Reply-To: <199407152358.TAA08861@bb.com>
Message-ID: <9407161648.AA19160@ah.com>
MIME-Version: 1.0
Content-Type: text/plain


   > When discussing complexity it is usual to use a measure of problem
   > size that corresponds to the physical size of the answer or
   > the question.

Not quite.  The length of the answer is not typically used in measures
of complexity.

The 'n' in O(n^2), et al., is the length of the input.  Exactly that,
and nothing more.  The length used is the number of symbols used to
encode the input from some finite alphabet of symbols.  Thus, the
lengths are determined up to a constant factor related to the
logarithm of the size of the alphabet.

   > Thus thus if you are factoring a 1024 bit number, n is 1024, not
   > 2^1024

Yes.  Getting the wrong 'n' will make complexity theory meaningless
and impenetrable.

Eric