# [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