Re: Directed Hamiltonian Path Problem

[tcmay@got.net (Timothy C. May)]

At 10:48 PM 11/28/95, E. ALLEN SMITH wrote:
>From:   IN%"perry@piermont.com" 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,
tcmay@got.net  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."