Number Theory is that part of mathematics that studies the properties of numbers. At its core lie the prime numbers. Starting with simple results like the prime decomposition, and simple algorithms like Euclid's algorithm, Number Theory builds up to ideas that underpin the security of the internet.
2 Clock Arithmetic
The key idea of clock arithmetic is to do your arithmetic as if on a clock face. When you go past , you “wrap around". Thus becomes , becomes , and so on. In clock arithmetic, then, which becomes . Thus we might write where the subscript stands for “clock arithmetic".
There's one slight difference with clock arithmetic in mathematics: we use instead of . Thus our clock face starts at and ends at . So .
We can also generalise to different clocks with different numbers. We could imagine a clock with only four numbers: . On this clock, we would have (since we wrap around twice).
Our notation gets a bit unwieldy here since it ought to record the “clock number". The proper notation is to write:
We read this as, for example, “ times is equivalent to modulo ".
As we're using correct notation, we should use correct terminology as well. The topic is known as modular arithmetic, not “clock arithmetic", and the clock number is known as the modulus.
If you think what is going on when doing the “wrap around", we can add or subtract multiples of the modulus without changing what it is equivalent to. So two numbers, say and , are equivalent modulo if divides their difference, .
We'll assume that modular arithmetic works. That is, there's never any ambiguity in working out the value of an expression.
3 Multiplication Tables
In modular arithmetic, there are only a finite number of “numbers". For example, with modulus then every number is equivalent to one of , , , or .
This means that we can write out all the possible multiplications in a multiplication table. For example, here's the multiplication table with modulus :
The row and column corresponding to is a bit dull, so we'll leave that out and just write:
Write out the multiplication table for a few moduli.
Some rows are “special" in that they have every number (other than ) on them. What characterises these rows?
Are there any moduli where every row is “special"?
Let's look at one of the “special" rows, for example the –row in the multiplication table for . Since each number appears there, we can say that for any number , there is some number such that .
Now in normal arithmetic, we would say that if then . We don't have fractions in modular arithmetic, but we can still say that if then there is some such that .
For each , find such that if then . What do you notice?
What is ? Is this a coincidence?
Hopefully you noticed that you got the same each time. In fact, in this case . It is a coincidence that but not a coincidence that .
Pick a “special" row in one of your other multiplication tables and repeat the above.
For a modulus where every row is special, write out a table pairing each number with its corresponding partner.
When we have this situation, we can “undo" multiplication. For example, working modulo (that is, with modulus ) then has this property. To undo multiplication by , we multiply by . So behaves like . Another way of writing is and we use this notation and refer to the reciprocal of . Thus: .
Our conclusion is that for every “special" modulus, then every non-zero number has a reciprocal and so we can “do division".
What about the non-special moduli? Which numbers do not have reciprocals?
Let's move on to powers. Just as with multiplication, we can do powers and write out a “power table". Also just as with multiplication, it makes sense to ignore powers of but we will include as our first column. We'll write it out up to , where is our modulus. Thus for our “power table" looks like this:
Write out the power table for a variety of moduli. What special features do you notice?
In this case, only some moduli have “special rows" where every number appears, but even when some rows are “special" then not every row is. A number such that , , , etc. generates all the numbers is called a primitive root.
Find primitive roots for the first few moduli that have them.
At the heart of modern cryptography lies the ability to have a secret conversation even in the presence of eavesdroppers. The key to this is that it is possible for two people to both know something without actually exchanging that information.
Let's see how this works. It is traditional for the two protagonists in cryptography to be called Alice and Bob. Let's keep the traditions.
In plain sight of everyone, Alice and Bob pick a nice prime number, say , and a smaller number, say . So everyone knows and , including any eavesdroppers.
Alice and Bob then each choose another number in secret.
So Alice chooses a number, say , and Bob chooses a number, say .
Alice and Bob each calculates the corresponding power of modulo .
So Alice calculates and Bob . Let's call these and respectively.
These two numbers are exchanged, again in plain sight.
Then Alice computes and Bob computes . The crucial fact is that these two produce exactly the same number, which is .
Alice and Bob can then use this number in some secret code, and any eavesdropper doesn't know either or so can't figure out .
Of course, given enough time and computing power, the evil eavesdropper could compute every single and eventually figure out and . Looking at your “power tables", you should see that there is no particular pattern to the numbers and so the eavesdropper would genuinely have to calculate them all. There is no quick method.
In practice, the numbers chosen are big enough that this is practically impossible.
Thus Alice and Bob have agreed on a number, , without anyone else knowing what it is even though their entire conversation could be overheard.
Carry out the exchange with a partner to agree on a “secret number".