Factoring

jamesd@netcom.com (James A. Donald) writes:
> n is the number of bits, and factoring can be done in considerably less
> than 2^(n/2)
>
> 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.
>
> Thus thus if you are factoring a 1024 bit number, n is 1024, not
> 2^1024

Ah.  Thank you -- it's amazing the number of obviously wrong answers
 I received to my question, all of them taking an authoritative tone
 (from "your algorithm doesn't work" (it does) to "your algorithm takes
 enormous amounts of memory" (in fact, it takes 3n)).

Makes one realize (again) how sceptical one must be towards answers 
 received on the 'net, "even" from cypherpunks.   [This isn't to
 slam anyone, just to suggest that people take a little more time to
 think before hitting the 'r' key.]
--
L. Todd Masco  | Bibliobytes books on computer, on any UNIX host with e-mail
cactus@bb.com  | "Information wants to be free, but authors want to be paid."

> 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