[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: [email protected]*Subject*: Re: Directed Hamiltonian Path Problem*From*: [email protected] (Timothy C. May)*Date*: Tue, 28 Nov 1995 18:02:42 -0800*Sender*: [email protected]

At 10:48 PM 11/28/95, E. ALLEN SMITH wrote: >From: IN%"[email protected]" 28-NOV-1995 02:02:17.85 > >Indeed. Its the problem with innumeracy. People don't understand that >if, say, a problem is O(2^N), and a problem of size 1000 requires a >liter of fluid, a problem of size 2000 requires >--------------------------- > Now that I've looked at it a bit more, I would definitely agree... >exponential growth is quite a function. Incidentally, talking about it in >liters of fluid is probably not the best way to look at it, any more than The reason we speak in terms of physical volumes of "Adleman computers" is to make concrete the way things scale. If the amount of Adleman computers needed to factor, say, a 2000-digit modulus (or some reasonably equivalent Hamiltonian cycle problem, such as the TSP) is "ten Pacific oceans full of them running for 100 years," then one has a pretty clear feel for just how futile it is to ask about "But what about if we apply MASSIVE PARALLELISM?!?!" (There's a certain well-known person who frequently raises the issue of "massive parallelism" on sci.crypt, each time revealing that he just doesn't understand that 1024 or even a million processors will not "solve" the problem for brute force attacks. Some people think there is something _magical_ about "massive parallelism.") >computer chips can be best defined in square centimeters. But that doesn't >change the essential conclusion; it just alters how big of a problem you >need to use. The lesson here, I believe, is to use as large of a key/etcetera >as possible... something that should be news to none, even to novices like me. >Never assume that something will require too much computing power, until the >computing power needed is not doable in the universe. Then add some, since >(for some problems) someone might figure out a clever way around them. I >worry that factoring may be one of these. I don't worry much about factoring breakthroughs. And I don't mean minor improvements, which keep occurring: I mean major breakthroughs which would make factoring a 2000-decimal-digit number "easy." Practically speaking, snarfing private keys is a helluva lot easier, for many reasons. --Tim May Views here are not the views of my Internet Service Provider or Government. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, [email protected] 408-728-0152 | anonymous networks, digital pseudonyms, zero Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^756839 | black markets, collapse of governments. "National borders are just speed bumps on the information superhighway."

- Prev by Date:
**Re: Directed Hamiltonian Path Problem** - Next by Date:
**Illustrations** - Prev by thread:
**Re: Directed Hamiltonian Path Problem** - Next by thread:
**Re: Directed Hamiltonian Path Problem** - Index(es):