Provably "Secure" Crypto (was: IPG Algorithm Broken!)
John Anonymous MacDonald
nobody at cypherpunks.ca
Tue Nov 26 09:43:14 PST 1996
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
More information about the Testlist
mailing list