The math is based on modular arithmetic, or cyclic math. What is Cyclic Math? The simplest math is arithmetic: we all learn how to add, subtract, multiply and divide. All these originate from counting. Let us begin with an example.
I have two answers, so I check with Google. Oops, there are 3 answers! For an interesting discussion, see【1】.
Anyway, most people will say weekday one is Monday. In math, this is expressed as a function: weekday(1) = Monday, weekday(2) = Tuesday, etc.
The next counting problem arises: should the index count from 1 or 0? That is, should we have weekday(7) as Sunday?
Math people opt for counting from 0. Programmers are math people, and they use an array, with square brackets [] marking the index: weekday[0] = Sunday, weekday[1] = Monday, etc.
This is the root of a programming quirk: when you define an array with n slots, and access each element by its index j, then a[j] is valid only for j = 0 to n - 1: using a[n] will lead to an "out of bound" or "out of range" error.
In summary, weekday counts are: 0, 1, 2, 3, 4, 5, 6 -- just 7 numbers. After that the counting repeats: that's cyclic math!
+ | 1 2 3 4 5 6 + (mod 7) | 1 2 3 4 5 6 --|----------------- -----------|------------ 1 | 2 3 4 5 6 7 1 | 2 3 4 5 6 0 2 | 3 4 5 6 7 8 2 | 3 4 5 6 0 1 3 | 4 5 6 7 8 9 3 | 4 5 6 0 1 2 4 | 5 6 7 8 9 10 4 | 5 6 0 1 2 3 5 | 6 7 8 9 10 11 5 | 6 0 1 2 3 4 6 | 7 8 9 10 11 12 6 | 0 1 2 3 4 5We don't need to show the trivial ones such as: 0 + 4 = 4, but 0 does appear as a sum: 2 + 5 becomes 0 in this system, because 7 is discarded, only the remainder 0 matters. For clarity, math people write this as: (2 + 5) mod 7 = 0, where 'mod 7' means 'under modulus 7', that is, remainder after division by 7.
Let x and y be any of the nonzero remainders of mod 7. The entry at row x and column y represents (x + y) for ordinary addition on the left, or (x + y) mod 7 for modular addition on the right. Since x + (y + 1) = (x + y) + 1, both tables can be constructed column by column. First, write down x: list vertically all the nonzero reminders of mod 7. The first column simply adds 1 to each of the leftmost, taking 7 as 0 for cyclic math. Then for each column y, add 1 to form the next column (y + 1), using cyclic math for the table on the right. Keep adding 1 for all the successive columns to produce the resulting tables.
Look again at (2 + 5) mod 7 = 0. This means, in cyclic math, or modular arithmetic, adding up can give a result zero. This is because two ants going in opposite directions will meet in this cyclic world. Indeed, in mod 7, +5 (forward 5 steps) is the same as -2 (backward 2 steps): -2 mod 7 = 5. Negative numbers can be converted to positive in modular arithmetic: -1 mod 7 = 6, -2 mod 7 = 5, etc. until -6 mod 7 = 1.
-1 mod 7 = 6, because (1 + 6) mod 7 = 0. -2 mod 7 = 5, because (2 + 5) mod 7 = 0. -3 mod 7 = 4, because (3 + 4) mod 7 = 0. -4 mod 7 = 3, because (4 + 3) mod 7 = 0. -5 mod 7 = 2, because (5 + 2) mod 7 = 0. -6 mod 7 = 1, because (6 + 1) mod 7 = 0.This enables modular subtraction to be done, using the idea: x - y = x + (- y).
Thus (4 - 3) mod 7 = (4 + (-3)) mod 7 = (4 + 4) mod 7 = 1. Of course, we could have done it faster: (4 - 3) mod 7 = 1 mod 7 = 1, but this just shows everything is consistent. Try doing (3 - 5) mod 7 in anyway you like.
So cyclic add and subtract can be done, with the result always within 0 to 6, the possible remainders of division by 7. How about the other arithmetic operations?
* | 1 2 3 4 5 6 * (mod 7) | 1 2 3 4 5 6 --|----------------- -----------|------------ 1 | 1 2 3 4 5 6 1 | 1 2 3 4 5 6 2 | 2 4 6 8 10 12 2 | 2 4 6 1 3 5 3 | 3 6 9 12 15 18 3 | 3 6 2 5 1 4 4 | 4 8 12 16 20 24 4 | 4 1 5 2 6 3 5 | 5 10 15 20 25 30 5 | 5 3 1 6 3 2 6 | 6 12 18 24 30 36 6 | 6 5 4 3 2 1Again, we don't need to show the trivial ones such as: 1 ⁎ 3 = 3. We can construct the multiplication tables column by column. Let x and y be any of the nonzero remainders of mod 7. The entry at row x and column y represents (x ⁎ y) for ordinary multiplication on the left, or (x ⁎ y) mod 7 for modular multiplication on the right. First write down x: list vertically all the nonzero reminders of mod 7, then apply x ⁎ (y + 1) = (x ⁎ y) + x. The first column is simply multiplying each by 1, so it is just a copy of the leftmost remainders. Then add this column y with the leftmost column x to form the next column (y + 1), using cyclic math, or mod 7 for table on the right. Keep adding with the leftmost column x for all the successive columns to produce the multiplication tables.
Note that 0 does not appear in the mod 7 multiplication table. Why?
Look at the remainders after division by 7. They are 0 to 6, all less than 7. Let x, y be two of them. If (x ⁎ y) mod 7 = 0, then (x ⁎ y) is a multiple of 7, or x ⁎ y = 7 ⁎ k for some number k. But 7 is as prime, meaning it cannot be broken further. Thus either x = 7, y = 1, or x = 1, y = 7, with k = 1. But this is impossible, as x and y are remainders less than 7.
As a result, (x ⁎ y) mod 7 is nonzero whenever x and y are nonzero. Putting this in another way:
Result #1: in mod 7 multiplication, the product of nonzeroes is nonzero.
Due to this, every row in the mod 7 multiplication table is distinct. For example, take the row with multiplier 3. The row consists of the products (3 ⁎ x) mod 7, for x from 1 to 6. What happens if (3 ⁎ x) mod 7 = (3 ⁎ y) mod 7, with y ≠ x but also from 1 to 6? Well, moving the right side to the left side, we have: (3 ⁎ (x - y)) mod 7 = 0 and y ≠ x means (x - y) ≠ 0. By Result #1, this is impossible!
Because x runs through all remainders, and (3 ⁎ x) mod 7 are all distinct, the row of multiplier 3 is a permutation of the remainders. This is true for every row, with the multiplier a remainder:
Result #2: each nonzero row of the mod 7 multiplication table is a permutation of the nonzero remainders.
In particular, 1 is nonzero, so 1 appears somewhere within each row. This means, for x from 1 to 6, there is always a y, also from 1 to 6, that gives (x ⁎ y) mod 7 = 1. Such a y is called the inverse of x in mod 7, denoted by y = (1/x) mod 7.
From the mod 7 multiplication table, we find:
(1/1) mod 7 = 1, because (1 * 1) mod 7 = 1. (1/2) mod 7 = 4, because (2 * 4) mod 7 = 1. (1/3) mod 7 = 5, because (3 * 5) mod 7 = 1. (1/4) mod 7 = 2, because (4 * 2) mod 7 = 1. (1/5) mod 7 = 3, because (5 * 3) mod 7 = 1. (1/6) mod 7 = 6, because (6 * 6) mod 7 = 1.Recall that -1 mod 7 = 6, thus (1/6) mod 7 = (1/-1) mod 7 = -1 mod 7 = 6, all good!
This enables modular division to be done for mod 7, using the idea: x / y = x ⁎ (1/y).
Of course the divisor y cannot be 0, or y is nonzero, and (1/y) mod 7 is defined. Thus (4 / 3) mod 7 = (4 ⁎ (1/3)) mod 7 = (4 ⁎ 5) mod 7 = 20 mod 7 = 6. To verify: (3 ⁎ 6) mod 7 = 18 mod 7 = 4. okey dokey.
So within mod 7, arithmetic poses no problem: cyclic add and subtract can be done, and cylic multiply and divide can be done, provided division by zero is forbidden. Let state this succinctly:
Result #3: mod 7 arithmetic is good: add, subtract, multiply and divide by nonzero all works fine.
For convenience, math people resue ⁎ for a binary operation in general, between symbols x, y, z, etc. When the symbols and the binary operation satisfy these properties:
Therefore, Result #2 becomes: nonzero mod 7 remainders form a group under modular multiplication, with identity 1. Of course, we can also verify this: all mod 7 remainders form a group under modular addition, with identity 0.
When a set of symbols has two binary operations, say + and ⁎, with the properties:
Moreover, if the condition (b) can be tightend to:
Therefore, Result #3 becomes: all mod 7 remainders form a field under modular addition and multiplication.
That is, like arithmetic, we can do all sorts of things for just 7 symbols: 0, 1, 2, 3, 4, 5, 6. Solve (4 ⁎ x + 2) mod 7 = 1 for x. Easy: x = (1 - 2)/4 mod 7 = -1/4 mod 7 = -2 mod 7 = 5. Can you verify the solution?
Are you brave enough to go further? I mean, go higher?
^ | 1 2 3 4 5 6 ^ (mod 7) | 1 2 3 4 5 6 --|------------------------- -----------|------------ 1 | 1 1 1 1 1 1 1 | 1 1 1 1 1 1 2 | 2 4 8 16 32 64 2 | 2 4 1 2 4 1 3 | 3 9 27 81 243 729 3 | 3 2 6 4 5 1 4 | 4 16 64 256 1024 4096 4 | 4 2 1 4 2 1 5 | 5 25 125 625 3125 15625 5 | 5 4 6 2 3 1 6 | 6 36 216 1296 7776 46656 6 | 6 1 6 1 6 1Again, we don't need to show the trivial ones such as: 40 = 1. To construct these tables column by column, let x be any of the nonzero remainders of mod 7. The entry at row x and column n represents (xn) for ordinary power on the left, or (xn) mod 7 for modular power on the right. First write down x: list vertically all the nonzero reminders of mod 7, then apply x(n + 1) = xn ⁎ x. The first column is simply raising each by power 1, so it is just a copy of the leftmost remainders. Then multiply this column n with the leftmost column x to form the next column (n + 1), using cyclic math, or mod 7 for table on the right. Keep multiplying with the leftmost column x for all the successive columns to produce the power tables, or exponentiation tables.
The rows are not distinct anymore. Note that the first row, the exponents of 1, are all 1: that's simple. However, the last column, of exponent 6 for every nonzero x, is always 1. Why?
To see this, recall Result #2: each nonzero row of the mod 7 multiplication table is a permutation of nonzero remainders.
Take x = 3. Then for y = 1 to 6, 3 ⁎ y is a permutation of 1 to 6 again. That is:
(3 * 1) mod 7 = 3 (3 * 2) mod 7 = 6 (3 * 3) mod 7 = 2 (3 * 4) mod 7 = 5 (3 * 5) mod 7 = 1 (3 * 6) mod 7 = 4Due to permutation, each nonzero appears once and only once on the right. Multiplying all of them and taking mod 7: (3 ⁎ 1) ⁎ (3 ⁎ 2) ⁎ (3 ⁎ 3) ⁎ (3 ⁎ 4) ⁎ (3 ⁎ 5) ⁎ (3 ⁎ 6) mod 7 = (3 ⁎ 6 ⁎ 2 ⁎ 5 ⁎ 1 ⁎ 4) mod 7
But the right-hand side is just z = (1 ⁎ 2 ⁎ 3 ⁎ 4 ⁎ 5 ⁎ 6) mod 7, since multiplication of numbers can be re-arranged and they form a permutation. For the left-hand side, we can take out all the 3's, and there are 6 of them. Therefore: (36 ⁎ z) mod 7 = z
Note that z is nonzero since it is the product of all nonzero in mod 7, by Result #1. So z has an inverse 1/z, which can be used to multiply both sides: (36 ⁎ z ⁎ 1/z) mod 7 = (z ⁎ 1/z) mod 7 = 1 mod 7 = 1
By property of multiplicative inverse, this simplifies to (36) mod 7 = 1 mod 7 = 1
This reasoning holds for any nonzero remainder x, therefore:
Result #4: for any nonzero remainder x, x6 mod 7 = 1.
The last result is first stated by a French mathematician, Pierre de Fermat, in 1640. Before 1940, everyone admires this result in number theory, but no one knows any use of it.
First, the mod 8 addition is nothing unusual:
+ | 1 2 3 4 5 6 7 + (mod 8) | 1 2 3 4 5 6 7 --|-------------------- -----------|-------------- 1 | 2 3 4 5 6 7 8 1 | 2 3 4 5 6 7 0 2 | 3 4 5 6 7 8 9 2 | 3 4 5 6 7 0 1 3 | 4 5 6 7 8 9 10 3 | 4 5 6 7 0 1 2 4 | 5 6 7 8 9 10 11 4 | 5 6 7 0 1 2 3 5 | 6 7 8 9 10 11 12 5 | 6 7 0 1 2 3 4 6 | 7 8 9 10 11 12 13 6 | 7 0 1 2 3 4 5 7 | 8 9 10 11 12 13 14 7 | 0 1 2 3 4 5 6and negatives of mod 8 can be computed:
-1 mod 8 = 7, because (1 + 7) mod 8 = 0. -2 mod 8 = 6, because (2 + 6) mod 8 = 0. -3 mod 8 = 5, because (3 + 5) mod 8 = 0. -4 mod 8 = 4, because (4 + 4) mod 8 = 0. -5 mod 8 = 3, because (5 + 3) mod 8 = 0. -6 mod 8 = 2, because (6 + 2) mod 8 = 0. -7 mod 8 = 1, because (7 + 1) mod 8 = 0.Thus in mod 8, we can perform addition and subtraction as before. However, mod 8 multiplication looks like this:
* | 1 2 3 4 5 6 7 * (mod 8) | 1 2 3 4 5 6 7 --|-------------------- -----------|-------------- 1 | 1 2 3 4 5 6 7 1 | 1 2 3 4 5 6 7 2 | 2 4 6 8 10 12 14 2 | 2 4 6 0 2 4 6 3 | 3 6 9 12 15 18 21 3 | 3 6 1 4 7 2 5 4 | 4 8 12 16 20 24 28 4 | 4 0 4 0 4 0 4 5 | 5 10 15 20 25 30 35 5 | 5 2 7 4 1 6 3 6 | 6 12 18 24 30 36 42 6 | 6 4 2 0 6 4 2 7 | 7 14 21 28 35 42 49 7 | 7 6 5 4 3 2 1The rows have repetitions, they are not permutations of the remainders. There are nonzero products giving 0. This is because 8 is not a prime, having 8 = 2 ⁎ 4, a product of two smaller numbers, and (2 ⁎ 4) mod 8 = 0.
Even worse, 1 does not appear in every row, meaning 1/x is undefined for some nonzero x. This is a disaster!
How to redeem from such a disaster? A Swiss mathematician Euler (pronounced oiler) who studied Fermat's Little Theorem found a way out, using the concept of relatively prime, or coprime.
We need to digress. A number is a prime if its only proper divisor is 1. The corresponding idea for a pair of numbers is their common divisor. Given a pair of numbers x and y, of course 1 is always a common divisor of them. If x and y are even, then 2 is a common divisor of both. In general, we are interested in their greatest common divisor, denoted by gcd(x,y). The ancient Greek mathematician Euclid, famous for his book of geometry, handed down an efficient method to compute gcd(x,y), but that is straying too far from our path.
Anyway, two numbers are coprime when their only common divisor is 1. In other words, x and y are coprime if and only if gcd(x,y) = 1.
What Euler discoverd is this: in the mod 8 multiplication table, if we pick out the remainders that are coprime to 8, the reduced table is actually quite nice!
First, determine which remainders are coprime to 8. There are only four: 1, 3, 5, 7, the odd ones:
* (mod 8)| 1 3 5 7
---------|--------
1 | 1 3 5 7
3 | 3 1 7 5
5 | 5 7 1 3
7 | 7 5 3 1
Now each row is a permutation of coprime remainders, and 1 appears in every row, giving:
(1/1) mod 8 = 1, because (1 * 1) mod 8 = 1. (1/3) mod 8 = 3, because (3 * 3) mod 8 = 1. (1/5) mod 8 = 5, because (5 * 5) mod 8 = 1. (1/7) mod 8 = 7, because (7 * 7) mod 8 = 1.Thus, as long as we stay within coprime remainders, division works fine. Recall the definition of a group, we have:
Result #5: in mod 8, remainders coprime to 8 form a group under multiplication.
How many symboles in this group, for mod n in general? This is counting how many remainders are coprime to n. Except for special cases of n (which we will see later on), there is no formula for it. Surely one can check every gcd(x,n) for x = 1 to (n-1). Math people used a symbol for this function, using the Greek letter phi: φ, and put a name on it: Euler's phi function: phi(n) = φ(n) = number of coprimes to n and not exceeding n.
For example, φ(8) = 4, as the odds are coprime to 8. We can investigate power in mod 8 for exponents up to φ(8):
^ | 1 2 3 4 ^ (mod 8) | 1 2 3 4 ---|-------------- ----------|-------- 1 | 1 1 1 1 1 | 1 1 1 1 3 | 3 9 27 81 3 | 3 1 3 1 5 | 5 25 125 625 5 | 5 1 5 1 7 | 7 49 343 2401 7 | 7 1 7 1The last column is 1 because of the same idea as before. Take row 5 from the mod 8 multiplication table. If we multiply 5 only to coprimes to 8:
(5 * 1) mod 8 = 5 (5 * 3) mod 8 = 7 (5 * 5) mod 8 = 1 (5 * 7) mod 8 = 3Multiplying all these equations, (54 ⁎ z) mod 8 = z, where z = (1 ⁎ 3 ⁎ 5 ⁎ 7) mod 8. Cancelling z, 54 mod 8 = 1.
Running through the same argument from Result #3 to Result #4, we have: Theorem #5 (Euler's generalisation of Fermat's Little Theorem): for x coprime to n, xφ(n) mod n = 1 for any nonzero n.
For a prime p, all nonzero remainders are coprime to p, thus φ(p) = p - 1, and we recover Fermat's Little Theorem.
In general, we have this property for Euler's ϕ function: Theorem #6: if two numbers n and m are coprime, ϕ(m ⁎ n) = ϕ(m) ⁎ ϕ(n).
We shall skip the proof of this result, as it requires some knowledge of number theory.
Applying this result, let n = p ⁎ q, a product of two different primes p and q. Then ϕ(n) = ϕ(p ⁎ q) = ϕ(p) ⁎ ϕ(q) = (p - 1) ⁎ (q - 1). For example, φ(6) = φ(2) ⁎ φ(3) = 1 ⁎ 2 = 2. Indeed, only 1 and 5 are coprime to 6 and not exceeding 6.
To outsiders like you and me, to understand RSA means to know:
Some years ago I have written a series Public Key Encryption. There are 5 parts, giving an in-depth explanation of the above questions based on the cyclic math we have learnt.
After that, I have also written a TiddlyWiki Prime Applications. The second application is "Prime for Secrets", which uses a slightly different method to explain cyclic math.
This graphic novel "The Imitation Game: Alan Turing Decoded"【2】chronicles his life and legend. It is a powerful, sympathetic portrait of one of the twentieth century's great minds. The novel touches on his view on math and algorithm: the idea of his universal machine (page 43).
The Enigma was a machine both for encrypting and decrypting, using the same key. The key would change at midnight, and the Germans were confident that the Enigma code was unbreakable for human.
Indeed it was, except that Turing broke it by a machine! He built essentially a special-purpose computer to search for the key, and applied ingenious mathematical tricks to reduce the search effort substantially.