[RC5] Fwd: MIT Cryptographic Effort

gindrup at okway.okstate.edu gindrup at okway.okstate.edu
Wed Nov 26 17:48:01 EST 1997


     Ah, "Cro-Magnon Search" -- pick an element at random.  If it's *the* 
     element stop.  Otherwise repeat.
     Running time analysis:
        Best: O(1)
        Average: O(n)
        Worst: O(infinity)
     It's related to "Cro-Magnon Sorting" -- randomly reorder the elements. 
     If the elements are now sorted, stop.  Otherwise, repeat.
     Running time analysis:
        Best: O(n) [you still have to check the ordering...]
        Average: O(n!)
        Worst: O(infinity)
     
     Note that although these algorithms have less than ideal worst case 
     and average running times, their probabilistic best case running time 
     is very short.  :)  Also, these algorithms are easy to implement, 
     given a suitable random number generator, say www.lavarand.sgi.com.
     
     Note also that these algorithms are easily distributed and suffer 
     immense average case speed-up through parallelization.
     
     To wit, given k clients where n >> k:
     Distributed Cro-Magnon Search:
     Break the search space into k (nearly equal) pieces.  Hand each piece 
     out to a different client each of whom runs Cro-Magnon Search on the 
     piece.  Terminate when one succeeds.  Run times: O(k), O(n/k), 
     O(infinity/k).
     
     Distributed Cro-Magnon Sort:
     Hand out the entire sort space to each client.  Have each client run 
     Cro-Magnon Sort on the entire sort space.  Terminate when one 
     succeeds.  Run times: O(kn), O(n!/k), O(infinity/k).
     
     Discussion:
        The large replication and transmission times of this version of 
     Cro-Magnon Sort and Search negatively impact the best case runtimes.  
     Worst case is little changed, but the average case experiences full 
     theoretical improvement from parallelization.  For this reason, "we" 
     recommend this algorithm for systems that are intended to be massively 
     parallel with very lazy programmers that have reliable random number 
     generators.
            -- Eric Gindrup ! gindrup at okway.okstate.edu


______________________________ Reply Separator _________________________________
Subject: RE: [RC5] Fwd: MIT Cryptographic Effort 
Author:  <rc5 at llamas.net > at SMTP
Date:    1997/11/26 14:54


On Wed, 26 Nov 1997, James  Kew wrote:
     
> >>>        http://rc5.mit.edu
> >
> >Well, that is entertaining.  9.8kks and my system is slugish, very 
> >slugish.
> 
> I get about 36kks on my P200 under IE4 Java VM; the Bovine client gets 
> about 230kks. Ho-hum.
     
For me the same, BUT: They finally decided to use Java, whereas 
Bovine is still denying Java. Keyword: v3.....
     
> What I *do* find interesting is their probablistic approach to finding 
> the key: no keyservers, just random searches.
Yep, that's true. But then there wont be anymore stats.....
     
Ivo
     
--
To unsubcribe, send 'unsubscribe rc5' to majordomo at llamas.net 
rc5-digest subscribers replace rc5 with rc5-digest
     


--
To unsubcribe, send 'unsubscribe rc5' to majordomo at llamas.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list