The Joy of Complexity

Rabin came up with a solution using what is now known as a ``one-way'' function. One-way functions translate into computational procedures. They are easy to compute in one direction, but hard to compute in the other. Familiar functions are not like this. For example, tripling a number is a two-way function, because it is easy to go from y to 3 times y. and also easy to go from z to z/3. Rabin used a one-way function developed by the mathematician John von Neumann:

Suppose you take a 100-digit number, X, and square it. This is easy to do by computer. You get a 200 digit number. Out of these 200 digits, you take the middle 100. Call the resulting number Y. Now if I give you X, you can calculate Y. But if I give you Y and ask you to calculate X, you have a much tougher time. Now do you see the idea?


Suppose the guards had some of the Y values and each spy had to memorize an X value.