Free Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers by John MacCormick, Chris Bishop Page B
Authors: John MacCormick, Chris Bishop
and (ii) the numbers start counting from 0 rather than 1.
The figure on the next page gives an example using the clock size 7. Note that the numbers on the clock are 0, 1, 2, 3, 4, 5, and 6. To do clock arithmetic with clock size 7, just add and multiply numbers together as normal—but whenever an answer is produced, you only count the remainder after dividing by 7. So to compute 12 + 6, we first do the addition as normal, obtaining 18. Then we notice that 7 goes into 18 twice (making 14), with 4 left over. So the final answer is
12 + 6 = 4 (clock size 7)
In the examples below, we'll be using 11 as the clock size. (As discussed later, the clock size in a real implementation would be much, much larger. We are using a small clock size to keep the explanation as simple as possible.) Taking the remainder after dividing by 11 isn't too hard, since the multiples of 11 all have repeated digits like 66 and 88. Here are a few examples of calculations with a clock size of 11:
7 + 9 + 8 = 24 = 2 (clock size 11)
8 × 7 = 56 = 1 (clock size 11)
The second math idea we need is power notation. This is nothing fancy: it's just a quick way of writing down lots of multiplications of the same number. Instead of writing 6 × 6 × 6 × 6, which is just 6 multiplied by itself 4 times in a row, you can write 6 4 . And you can combine power notation with clock arithmetic. For example,
Left: When using a clock size of 7, the number 12 is simplified to the number 5—just start at zero and count 12 units in a clockwise direction, as shown by the arrow. Right: Again using a clock size of 7, we find that 12 + 6 = 4—starting at 5, where we ended in the left figure, add on another 6 units in clockwise direction.
The table on the following page shows the first ten powers of 2, 3, and 6 when using clock size 11. These will be useful in the example we're about to work through. So before plunging on, make sure you're comfortable with how this table was generated. Let's take a look at the last column. The first entry in this column is 6, which is the same thing as 6 1 . The next entry represents 6 2 , or 36, but since we're using clock size 11 and 36 is 3 more than 33, the entry in the table is a 3. To calculate the third entry in this column, you might think that we need to work out 6 3 = 6 ? 6 ? 6, but there is an easier way. We have already computed 6 2 for the clock size we're interested in—it turned out to be 3. To get 6 3 , we just need to multiply the previous result by 6. This gives 3 × 6 = 18 = 7 (clock size 11). And the next entry is 7 × 6 = 42 = 9 (clock size 11), and so on down the column.
OK, we are finally ready to establish a shared secret, as used by computers in real life. As usual, you and Arnold will be trying to share a secret, while Eve eavesdrops and tries to work out what the secret is.
Step 1. You and Arnold each separately choose a private number.
This table shows the first ten powers of 2, 3, and 6 when using clock size 11. As explained in the text, each entry can be computed from the one above it by some very simple arithmetic.
To keep the math as easy as possible, we'll use very small numbers in this example. So suppose you choose 8 as your private number, and Arnold chooses 9. These two numbers—8 and 9—are not themselves shared secrets, but just like the private colors you chose in the paint-mixing trick, these numbers will be used as ingredients to “mix up” a shared secret.
Step 2. You and Arnold publicly agree on two public numbers: a clock size (we'll use 11 in this example) and another number, called the base (we'll use the base 2).
These public numbers—11 and 2—are analogous to the public color that you and Arnold agreed on at the start of the paint-mixing trick. Note that the paint-mixing analogy does break down a little here: whereas we needed only one public color, two public numbers are needed.
Step 3. You and Arnold each separately create a public-private number (PPN) by mixing up your
The figure on the next page gives an example using the clock size 7. Note that the numbers on the clock are 0, 1, 2, 3, 4, 5, and 6. To do clock arithmetic with clock size 7, just add and multiply numbers together as normal—but whenever an answer is produced, you only count the remainder after dividing by 7. So to compute 12 + 6, we first do the addition as normal, obtaining 18. Then we notice that 7 goes into 18 twice (making 14), with 4 left over. So the final answer is
12 + 6 = 4 (clock size 7)
In the examples below, we'll be using 11 as the clock size. (As discussed later, the clock size in a real implementation would be much, much larger. We are using a small clock size to keep the explanation as simple as possible.) Taking the remainder after dividing by 11 isn't too hard, since the multiples of 11 all have repeated digits like 66 and 88. Here are a few examples of calculations with a clock size of 11:
7 + 9 + 8 = 24 = 2 (clock size 11)
8 × 7 = 56 = 1 (clock size 11)
The second math idea we need is power notation. This is nothing fancy: it's just a quick way of writing down lots of multiplications of the same number. Instead of writing 6 × 6 × 6 × 6, which is just 6 multiplied by itself 4 times in a row, you can write 6 4 . And you can combine power notation with clock arithmetic. For example,
Left: When using a clock size of 7, the number 12 is simplified to the number 5—just start at zero and count 12 units in a clockwise direction, as shown by the arrow. Right: Again using a clock size of 7, we find that 12 + 6 = 4—starting at 5, where we ended in the left figure, add on another 6 units in clockwise direction.
The table on the following page shows the first ten powers of 2, 3, and 6 when using clock size 11. These will be useful in the example we're about to work through. So before plunging on, make sure you're comfortable with how this table was generated. Let's take a look at the last column. The first entry in this column is 6, which is the same thing as 6 1 . The next entry represents 6 2 , or 36, but since we're using clock size 11 and 36 is 3 more than 33, the entry in the table is a 3. To calculate the third entry in this column, you might think that we need to work out 6 3 = 6 ? 6 ? 6, but there is an easier way. We have already computed 6 2 for the clock size we're interested in—it turned out to be 3. To get 6 3 , we just need to multiply the previous result by 6. This gives 3 × 6 = 18 = 7 (clock size 11). And the next entry is 7 × 6 = 42 = 9 (clock size 11), and so on down the column.
OK, we are finally ready to establish a shared secret, as used by computers in real life. As usual, you and Arnold will be trying to share a secret, while Eve eavesdrops and tries to work out what the secret is.
Step 1. You and Arnold each separately choose a private number.
This table shows the first ten powers of 2, 3, and 6 when using clock size 11. As explained in the text, each entry can be computed from the one above it by some very simple arithmetic.
To keep the math as easy as possible, we'll use very small numbers in this example. So suppose you choose 8 as your private number, and Arnold chooses 9. These two numbers—8 and 9—are not themselves shared secrets, but just like the private colors you chose in the paint-mixing trick, these numbers will be used as ingredients to “mix up” a shared secret.
Step 2. You and Arnold publicly agree on two public numbers: a clock size (we'll use 11 in this example) and another number, called the base (we'll use the base 2).
These public numbers—11 and 2—are analogous to the public color that you and Arnold agreed on at the start of the paint-mixing trick. Note that the paint-mixing analogy does break down a little here: whereas we needed only one public color, two public numbers are needed.
Step 3. You and Arnold each separately create a public-private number (PPN) by mixing up your
Similar Books
The Book of Even More Awesome
Neil Pasricha
To Sin With A Stranger
Kathryn Caskie
Cold Ennaline
RJ Astruc
They Think You're Stupid
Herman Cain
Self's punishment
Bernhard Schlink
Fury
Salman Rushdie
Burned Hearts
Calista Fox
Swords of Arabia: Betrayal
Anthony Litton
Dangerous Talents
Frankie Robertson