Lesson 1 of 4

Clock arithmetic.

About 20 minutes · 6 practice questions

Read the full article: Cryptography

Modular arithmetic: a remainder as a place on a clock, addition that wraps back to zero, and powers that leap around the dial and in the end return to 1.

Step 1 of 6 · Remainders

Step 1 of 6

Remainders

Today’s encryption is built on arithmetic in which numbers never grow: they wrap round. When you divide a whole number $a$ ⁠ by a number $n$ ⁠, a remainder between $0$ ⁠ and $n - 1$ ⁠ is left. That remainder is written $a \bmod n$ ⁠, read “ $a$ ⁠ mod $n$ ⁠”.

In the Scene, Alice and Bob are at either end of an open tube, and Eve listens in the middle. Look inside is open at The maths: in the middle of the board stands a dial with $23$ ⁠ places, $0$ ⁠ to $22$ ⁠, like a clock. Every number lands on the place of its remainder on dividing by $23$ ⁠.

To the question

Step 2 of 6

Round the clock

An ordinary clock is arithmetic mod $12$ ⁠: after $11$ ⁠ comes $0$ ⁠ again, which we call $12$ ⁠. To know the time in a few hours, add and take the remainder. The same works for multiplication: you can take the remainder after every step, and the result does not change.

To the question

Step 3 of 6

Powers mod p

A key exchange does not add but raises to powers. Choose a prime $p$ ⁠, here $23$ ⁠, and a number $g$ ⁠, here $5$ ⁠. Alice chooses a secret number $a$ ⁠ and works out

$A = g^a \bmod p$ ⁠

Alice’s secret is now fixed at $a = 2$ ⁠, and the maths is hidden. Work out $A$ ⁠ yourself.

To the question

Step 4 of 6

Step by step

There is no need to work out $5^{10}$ ⁠, an eight-digit number, to know what $5^{10} \bmod 23$ ⁠ is. Each power is the one before times $g$ ⁠, and you can take the remainder after every multiplication. That way the numbers always stay smaller than $p$ ⁠, and that is how powers of numbers hundreds of digits long are worked out too.

Change Alice’s secret and watch her board and her hand on the dial.

To the question

Step 5 of 6

Leaps

The powers of $5$ ⁠ mod $23$ ⁠ do not rise in order: $5$ ⁠, $2$ ⁠, $10$ ⁠, and then a jump. The hand leaps around the dial, and there is no way to know where it will land without working it out.

To the question

Step 6 of 6

A full circle

Mod $23$ ⁠, $5$ ⁠ has a special property: its powers reach every place on the dial except $0$ ⁠, each place once. Such a number is called a generator. In the last Lesson of this Unit it will be the $g$ ⁠ of the key exchange.

To the question

Interactive scene

Loading the interactive version…

Each step sets up the Scene for you, and a control marked “fixed” stays put for that step.

To the experiment

Practice · Calculate

What is $17 \bmod 5$ ⁠?

To the experiment

Practice · Calculate

The clock shows $9$ ⁠. What will it show in $8$ ⁠ hours? (On a $12$ ⁠-hour clock, with $12$ ⁠ written here as $0$ ⁠.)

To the experiment

Practice · Calculate

The arithmetic runs mod $p = 23$ ⁠, with $g = 5$ ⁠. Alice’s secret is fixed at $a = 2$ ⁠. What does she send, $A = 5^2 \bmod 23$ ⁠?

To the experiment

Practice · Reach the target

Change Alice’s secret until $A = 5^a \bmod 23$ ⁠ is $10$ ⁠, then press Check.

To the experiment

Practice · Predict, then look

At $a = 3$ ⁠, $A = 10$ ⁠. What will $A$ ⁠ be when Alice’s secret goes up to $a = 4$ ⁠? Write a number, and then the Scene moves to $a = 4$ ⁠.

To the experiment

Practice · Predict, then look

The powers of $5$ ⁠ mod $23$ ⁠ leap around the dial. What will $A = 5^{22} \bmod 23$ ⁠ be? Choose, and then Alice’s secret moves to $22$ ⁠.