From: nobody@cypherpunks.ca (John Anonymous MacDonald)
Date: Tue, 26 Nov 1996 09:43:14 -0800 (PST)
To: cypherpunks@toad.com
Subject: Re: Provably "Secure" Crypto (was: IPG Algorithm Broken!)
Message-ID: <199611261728.JAA14047@abraham.cs.berkeley.edu>
MIME-Version: 1.0
Content-Type: text/plain



At 7:39 PM 11/25/1996, The Deviant wrote:
>> Rigorous proofs of the non-existence of an algorithm are not new.  
>> Neither are rigorous proofs that any algorithm which can solve a given 
>> problem requires a minimal running time.  Or, in an even stronger sense, 

>Hrmmm... I seem to see a problem (namely Moore's first law) in assigning
>anything a "minimal running time".  Perhaps "minimal instruction count"
>would be more suited to your example.  Because if you're talking about
>time, it essentially boils down to "the longer something takes the less
>time it takes".

"Introduction to Algorithms" by Cormen, Leiserson, and Rivest is a
good introduction to Big O notation.  The problem you raise is the
motivation behind this notation.

diGriz