One Time Pad (was: Re: [rc5] The DOS client appears at last!)

wooledge at kellnet.com wooledge at kellnet.com
Tue Oct 28 21:51:08 EST 1997


Ranjit Annamalai (rxa21 at po.cwru.edu) wrote:

> I remember reading a month or so ago about some people who had come up
> with some new algorithms.  One was for searching, they say in a binary
> tree, you only have to search half the tree (thats correct isn't it?)

In a balanced binary tree of N nodes, you will find the node for which
you're searching after at most log2(N) steps (that's "log base 2").  The
worst case binary tree is a linked list, which will require N steps.

In computer science terms, we speak of the "order" of an operation.  In
the balanced binary tree search, the algorithm takes O(log2(N)) time
(that's "order of log base 2 of N").  Basically this means that the
average time required to find a node is proportional to the log base 2
of N.  (Whether each step takes 1 microsecond or 10 seconds is not
considered. :-/)

> but this new algorigthm allowed you search 1/10th of the tree to find
> your answer.

I assume you read that the algorithm was O(log10(N)).  This is certainly
possible to do -- just envision a tree where each node has 10 children
instead of 2 (a "decimal" tree, I guess).  You could store numbers this
way if you write them out in decimal and then index them by their digits.
(If the numbers are stored as strings -- serial numbers, for example --
then this might be natural.)

This sort of thing is common with word lookups.  For instance, consider
a dictionary stored like this: when looking up a word, you take the first
letter; this takes you to the first "level".  If your word is one letter
long then you're in the right place, so your definition should be here.
If not, you take the second letter and go on to the second "level".
Thus, each node of this tree would have up to 26 children in the English
alphabet (more or less in other languages).  When looking up a word
with 7 letters, you only need to go through 7 "levels", no matter how
big the dictionary is.

>I thought the other answer was for breaking encryption
> which allowed exponential increases in the likelihood of finding a key
> when using brute force.

The brute force algorithm for searching through keys is O(2^N) for
N-bit encryption.  This is exponential growth -- *against* us!

-- 
------------                  Greg Wooledge                  -------------
-------                   wooledge at kellnet.com                     -------
---              http://kellnet.com/wooledge/main.html                 ---
----
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.



More information about the rc5 mailing list