Free Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers by John MacCormick, Chris Bishop

“pretend” math. The real point is that to translate the paint-mixing trick into numbers, we need a one-way action: something that can be done , but can't be undone. In the paint-mixing trick the one-way action was “mixing paint.” It's easy to mix some paints together to form a new color, but it's impossible to “unmix” them and get the original colors back. That's why paint-mixing is a one-way action.
    We found out earlier that we would be using some pretend math. Here is what we are going to pretend: multiplying two numbers together is a one-way action. As I'm sure you realize, this is definitely a pretense. The opposite of multiplication is division, and it's easy to undo a multiplication just by performing a division. For example, if we start with the number 5 and then multiply it by 7, we get 35. It's easy to undo this multiplication by starting with 35 and dividing by 7. That gets us back to the 5 we started with.
    But despite that, we are going to stick with the pretense and play another game between you, Arnold, and Eve. And this time, we'll assume you all know how to multiply numbers together, but none of you knows how to divide one number by another number. The objective is almost the same as before: you and Arnold are trying to establish a shared secret, but this time the shared secret will be a number rather than a color of paint. The usual communication rules apply: all communication must be public, so Eve can hear any conversations between you and Arnold.
    OK, now all we have to do is translate the paint-mixing trick into numbers:
    Step 1. Instead of choosing a “private color,” you and Arnold each choose a “private number.”
    Let's say you choose 4 and Arnold chooses 6. Now think back to the remaining steps of the paint-mixing trick: announcing the public color, making a public-private mixture, publicly swapping your public-private mixture with Arnold's, and finally adding your private color to Arnold's public-private mixture to get the shared secret color. It shouldn't be too hard to see how to translate this into numbers, using multiplication as the one-way action instead of paint-mixing. Take a couple of minutes to see if you can work out this example for yourself, before reading on.
    The solution isn't too hard to follow; you've already both chosen your private numbers (4 and 6), so the next step is
    Step 2. One of you announces a “public number” (instead of the public color in the paint-mixing trick).
    Let's say you choose 7 as the public number.
    The next step in the paint-mixing trick was to create a public-private mixture. But we already decided that instead of mixing paints we would be multiplying numbers. So all you have to do is
    Step 3. Multiply your private number (4) and the public number (7) to get your “public-private number,” 28.
    You can announce this publicly so that Arnold and Eve both know your public-private number is 28 (there's no need to carry pots of paint around anymore). Arnold does the same thing with his private number: he multiplies it by the public number, and announces his public-private number, which is 6 × 7, or 42. The figure on the following page shows the situation at this point in the process.
    Remember the last step of the paint-mixing trick? You took Arnold's public-private mixture, and added a pot of your private color to produce the shared secret color. Exactly the same thing happens here, using multiplication instead of paint-mixing:
    Step 4. You take Arnold's public-private number, which is 42, and multiply it by your private number, 4, which results in the shared secret number , 168.
    Meanwhile, Arnold takes your public-private number, 28, and multiplies it by his private number, 6, and—amazingly—gets the same shared secret number, since 28 × 6 = 168. The final result is shown in the figure on the facing page.

    The number-mixing trick, step 3: The public-private numbers are available to anyone who wants them.
    Actually, when you think