Most public key systems rely on number-theoretic results. Before we can discuss the implementation of one, we need to quickly go over the necessary background. We have already used a tiny amount of number theory (in our discussion of computing mod p and of the greatest common divisor). Of course, this must be done briefly, and we will only touch on a small part of a large and ancient field-- the interested reader would do well to consult a text on number theory (e.g. [NZM], [Ros]) for more information.
We have already met the greatest common divisor, or gcd, which is the largest integer which divides both of a pair of numbers. Two numbers are said to be relatively prime if their greatest common divisor is 1. As we have already seen, finding two relatively prime numbers has important applications in many cryptosystems.
How can we determine the gcd of two numbers? If the numbers are not too large, just looking at their factors does the trick. For example,
One such algorithm is the Euclidean algorithm, which has been around for thousands of years. It works by computing successive differences-- to compute gcd(a, b), where a > b, we first compute r1 = a - k1b, where k1b is the largest multiple of b that is less than a. Then we repeat this, finding r2 = b - k2r1, r3 = r1 - k3r2, and so on until the remainder is zero. The last nonzero remainder is the gcd. For example, to calculate gcd(138, 126),
|b - 10r1||=||-10a||+11b||=||6||=||r2|
|r1 - 2r2||=||21a||-23b||=||0|
This not only gives gcd(138, 126) = 6, but expresses it as a difference of multiples of the two numbers: 6 = 11×126 - 10×138. We can write this procedure more formally as a theorem.
We have already seen that the Euclidean algorithm also gives us the following:
Why does the Euclidean Algorithm work? It follows from the observation that if a = bk + r, then gcd(a, b) = gcd(b, r). For example, gcd(138, 126) = gcd(126, 12) = gcd(12, 6) = 6. We write this as a lemma.
Let d = gcd(a, b). Then since d is a divisor of a and a divisor of b, it is also a divisor of a - bk. Since r = a - bk, we have d a divisor of r. So it must divide gcd(b, r).
Now, in order to prove equality, we want to show that also gcd(b, r) is a divisor of d. Certainly gcd(b, r) divides a, since a = r + bk. It also divides b, and so we have gcd(b, r) as a divisor of gcd(a, b).
Thus, gcd(b, r) = gcd(a, b).
Now we are ready to prove that the Euclidean Algorithm (Thm. 10.1) always yields the greatest common divisor.
Notice that the sequence b > r1 > r2 > r3 >... is a strictly decreasing sequence of positive integers, so it must eventually terminate with some rn > 0. The last equation can be written as kn + 1rn = rn - 1, and so rn is a divisor of rn - 1. Then certainly rn = gcd(rn, rn - 1). Applying the lemma to the equation above it, we obtain gcd(rn, rn - 1) = gcd(rn - 1, rn - 2). Repeating in this way, we obtain rn = gcd(rn, rn - 1) = gcd(rn - 1, rn - 2) =...= gcd(r1, b) = gcd(a, b).
Recall that if r is such that ar 1 (mod n), then r is called the multiplicative inverse of a modulo n. We have already dealt with such objects extensively. We now state a theorem which tells us exactly when such inverses exist. Note that this is really just Prop. 7.1 slightly reworded.
First, suppose that a has an inverse modulo n. Then there is a k so that
Now suppose that gcd(a, n) = 1. Then again using Cor. 10.2, there are integers r and s with ar + ns = 1. This means ar - 1 is divisible by n, so
It is common (and quite convenient) to denote the set of integers modulo n as . That is,
We will use to denote the elements of which have multiplicative inverses. In light of the last theorem, we have
In this section, we state a very old theorem about simultaneous solutions to congruences. This theorem may have been known to the eight-century Buddhist monk I-Hsing, and certainly appears in Ch'in Chiu-shao's Mathematical Treatise in Nine Sections, written in 1247. It is sometimes (rarely) referred to as the ``Formosa Theorem''.
As an example of this, suppose five kids pool all their money and buy a bag of candy. They divide the candy up evenly, and find there are 3 pieces left over. Suddenly, one kid's mom comes out, tells him ``no candy before dinner'', and hauls him off. The other four kids divide up the candy and there is one piece left over. While they are squabbling over it, a dog runs up and eats the disputed piece.
The Chinese Remainder Theorem tells us that we can always determine how many pieces of candy were in the bag, at least up to multiples of 20. In the above example, there were 13 pieces of candy (or 33, or 53, or ...). If we want to solve this problem with Maple, the command chrem([3,1],[5,4]) does the trick. We could also use numtheory[mcombine](5,3,4,1).
Since m and n are relatively prime, there are integers k and t so that mk + nt = 1. Then
To check uniqueness, suppose there are two solutions c and d. Since c a (mod m) and d a (mod m), we have c - d 0 (mod m). Similarly, c - d 0 (mod n). Since both m and n divide c - d, and m and n are relatively prime, we have that mn divides c - d. Thus c - d 0 (mod mn), that is, c d (mod mn).
In this and future sections, we shall use the notation ab to denote a mod b.
First, let's take a look at a few examples of what happens when we reduce the sequence a, a2, a3, a4,... modulo n. Consider 3k20:
The sequence consists of four numbers 3, 9, 7, 1 and then it repeats. What about 4? We have
This is also periodic, but notice that we never get back to 1. Similarly, let's look at the powers of 6:
This gets stuck at 16. Finally, consider the powers of 11:
This sequence is periodic of period 2, and contains 1.
We can readily categorize the elements with finite order. If you look at the examples above, 3 and 11 have finite order mod 20, while 4 and 6 do not. You probably have already guessed that this is because gcd(3, 20) = 1 and gcd(11, 20) = 1, while gcd(4, 20) = 4 and gcd(6, 20) = 2.
First, suppose a has finite order mod n. Then there is some k so that
Now we suppose gcd(a, n) = 1, and we want to find the inverse of a. Consider the sequence
So, we have seen that any invertible element of has finite order. In particular, if p is a prime number, every element except 0 is invertible and so has finite order. What are the possible orders? A theorem of Pierre de Fermat gives a result in that direction.
Among other things, this theorem says that if p is prime, then the order of a mod p always divides p - 1. Note that it doesn't say the order is p - 1, just that it is a divisor of it. Also, it says nothing about order with modulo a non-prime. We won't give the proof of this theorem here. Rather, we will give a proof of a more general result in the next section.
Recall that we denote the set of invertible elements of by . That is,
We can compute a few values of (n) just by counting.
|(5)||=||4||since||=||1, 2, 3, 4|
|(7)||=||6||since||=||1, 2, 3, 4, 5, 6|
|(8)||=||4||since||=||1, 3, 5, 7|
|(9)||=||6||since||=||1, 2, 4, 5, 7, 8|
|(10)||=||4||since||=||1, 3, 7, 9|
|(11)||=||10||since||=||1, 2, 3, 4, 5, 6, 7, 8, 9, 10|
|(12)||=||4||since||=||1, 5, 7, 11|
Of course, Maple also knows about the function in the numtheory package, so we could generate more values by asking Maple. But let's try to understand a bit more. We can readily prove some properties of .
(a) This is immediate, since all non-zero elements of 0, 1,..., p-1 are invertible.
(b) We prove this part just by counting. Since p is prime, the only numbers in which are not relatively prime to pn are multiples of p. These are 0, p, 2p, 3p,..., p2,(p + 1)p,...,(pn - 1 - 1)p. Note that pn - 1p = pn, so there are exactly pn - 1 multiples of p less than pn (including 0). All the others are relatively prime to p-- this gives the result.
(c) We need to show that the number of elements in is the same as the product of the size of and . We do that by showing that for each t , there is exactly one pair (r, s) with r and s .
So, let r and s . Then, by the Chinese Remainder Theorem (Thm. 10.5), there is an integer t < ab with
Now take t , and we must find a corresponding r and s. Let r = ta. Now, since gcd(t, ab) = 1, certainly gcd(t, a) = 1. Since r t mod a, there is an integer k so that t = r + ka, so we have gcd(r, a) = 1. Thus r . Similarly, we let s = tb, and we see that s .
Since we have paired each t with a unique pair (r, s) ×Zb*, they have the same cardinality. The first set has (ab) elements, and the latter has (a)(b).
We now come to Euler's generalization of Fermat's result. This result is the central idea underlying the RSA public key cryptosystem.
Let a be relatively prime to n, and consider the set
Now, multiply all the elements of together; call the result N. Then Nn . If we multiply all the elements of a together, we get a(n)N, and since the two sets are the same, we have