Provably "Secure" Crypto (was: IPG Algorithm Broken!)

[John Anonymous MacDonald]

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