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."