Some Number Theory

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.

The greatest common divisor and the Euclidean algorithm

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,

gcd(138, 126) = 6    since     138 = 2 ^. 3 ^. 23   and   126 = 2 ^. 3^{2 .} 7.

However, there must be a more efficient way, since Maple can calculate the gcd of two 60-digit numbers in well under a second, while taking a long time (about 10 minutes on a 600 Mhz pentium computer) to factor either one of them.

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 r₁ = a - k₁b, where k₁b is the largest multiple of b that is less than a. Then we repeat this, finding r₂ = b - k₂r₁, r₃ = r₁ - k₃r₂, and so on until the remainder is zero. The last nonzero remainder is the gcd. For example, to calculate gcd(138, 126),

		a		=	138
			b	=	126
		a	- b	=	12	=	r1
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 > r₁ > r₂ > r₃ >... is a strictly decreasing sequence of positive integers, so it must eventually terminate with some r_n > 0. The last equation can be written as k_{n + 1}r_n = r_{n - 1}, and so r_n is a divisor of r_{n - 1}. Then certainly r_n = gcd(r_n, r_{n - 1}). Applying the lemma to the equation above it, we obtain gcd(r_n, r_{n - 1}) = gcd(r_{n - 1}, r_{n - 2}). Repeating in this way, we obtain r_n = gcd(r_n, r_{n - 1}) = gcd(r_{n - 1}, r_{n - 2}) =...= gcd(r₁, b) = gcd(a, b).

Recall that if r is such that ar $\equiv$ 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

ak $$\equiv$$ 1 (mod n).

In particular, n is a divisor of ak - 1, so there must be some integer t so that ak - 1 = nt. Rewriting this as

ak - nt = 1,

we see that gcd(a, n) = 1 (by Cor. 10.2).

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

ar $$\equiv$$ 1 (mod n).

But this says that r is the inverse of a modulo n.

It is common (and quite convenient) to denote the set of integers modulo n as $\Z_{n}^{}$. That is,

$$\Z_{n}^{}$$ = $$\set$$0, 1, 2,..., n-1

As we already know, this set is closed under addition and multiplication, and the usual associative, distributive, and commutativity laws hold. This set is an example of an algebraic structure called a ring.

We will use $\Z_{n}^{*}$ to denote the elements of $\Z_{n}^{}$ which have multiplicative inverses. In light of the last theorem, we have

$$\Z_{n}^{*}$$ = $$\set$$a $$\in$$ $$\Z_{n}^{}$$$$\st$$gcd(a, n)=1

For example,

$$\Z_{7}^{*}$$ = $$\set$$1, 2, 3, 4, 5, 6        $$\Z_{8}^{*}$$ = $$\set$$1, 3, 5, 7        $$\Z_{12}^{*}$$ = $$\set$$1, 5, 7, 11

The Chinese Remainder Theorem

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

c = bkm + ant

is the desired solution. To verify this, we need only check:

c $$\equiv$$ ant $$\equiv$$ a(1 - mk) $$\equiv$$ a  (mod m)

and

c $$\equiv$$ bkm $$\equiv$$ b(1 - nt) $$\equiv$$ b  (mod n)

To check uniqueness, suppose there are two solutions c and d. Since c $\equiv$ a (mod m) and d $\equiv$ a (mod m), we have c - d $\equiv$ 0 (mod m). Similarly, c - d $\equiv$ 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 $\equiv$ 0 (mod mn), that is, c $\equiv$ d (mod mn).

Powers modulo n

In this and future sections, we shall use the notation $\modn$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, a², a³, a⁴,... modulo n. Consider $\modn$3^k20:

3, $$\modn$$3²20 = 9, $$\modn$$3³20 = 7, $$\modn$$3⁴20 = $$\modn$$2120 = 1, $$\modn$$3⁵20 = 3,...

The sequence consists of four numbers 3, 9, 7, 1 and then it repeats. What about 4? We have

4, $$\modn$$4²20 = 16, $$\modn$$4³20 = 4, $$\modn$$4⁴20 = 16,...

This is also periodic, but notice that we never get back to 1. Similarly, let's look at the powers of 6:

6, $$\modn$$6²20 = $$\modn$$3620 = 16, $$\modn$$6³20 = $$\modn$$16 ^. 620 = $$\modn$$9620 = 16, $$\modn$$6⁴20 = 16,...

This gets stuck at 16. Finally, consider the powers of 11:

11, $$\modn$$11²20 = $$\modn$$12120 = 1, $$\modn$$11³20 = 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

1 = $$\modn$$a^kn = $$\modn$$an ^. $$\modn$$a^{k - 1}n.

Thus, a has a multiplicative inverse, namely a^k-1n. By Thm. 10.4, this means gcd(a, n) = 1.

Now we suppose gcd(a, n) = 1, and we want to find the inverse of a. Consider the sequence

a,$$\modn$$a²n,$$\modn$$a³n,...,$$\modn$$aⁿn,$$\modn$$a^{n + 1}n.

Since there are n + 1 elements and we are reducing modulo n, there must be at least two which are equal. Let's denote these by $\modn$a^kn and $\modn$a^tn, with 1$\le$t < k. Since

$$\modn$$a^kn = $$\modn$$a^tn

we have

$$\modn$$a^{k - t}n = 1.

Thus, a has order k - t mod n.

So, we have seen that any invertible element of $\Z_{n}^{}$ 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.

The Euler $\varphi$-function and Euler's Theorem

Recall that we denote the set of invertible elements of $\Z_{n}^{}$ by $\Z_{n}^{*}$. That is,

$$\Z_{n}^{*}$$ = $$\set$$a $$\in$$ Z_n$$\st$$gcd(a, n)=1.

This set is sometimes called a reduced residue system modulo n.

We can compute a few values of $\varphi$(n) just by counting.

$$\varphi$$(2)	=	1	since	$$\Z_{2}^{*}$$	=	$$\set$$1
$$\varphi$$(3)	=	2	since	$$\Z_{3}^{*}$$	=	$$\set$$1, 2
$$\varphi$$(4)	=	2	since	$$\Z_{4}^{*}$$	=	$$\set$$1, 3
$$\varphi$$(5)	=	4	since	$$\Z_{5}^{*}$$	=	$$\set$$1, 2, 3, 4
$$\varphi$$(6)	=	2	since	$$\Z_{6}^{*}$$	=	$$\set$$1, 5
$$\varphi$$(7)	=	6	since	$$\Z_{7}^{*}$$	=	$$\set$$1, 2, 3, 4, 5, 6
$$\varphi$$(8)	=	4	since	$$\Z_{8}^{*}$$	=	$$\set$$1, 3, 5, 7
$$\varphi$$(9)	=	6	since	$$\Z_{9}^{*}$$	=	$$\set$$1, 2, 4, 5, 7, 8
$$\varphi$$(10)	=	4	since	$$\Z_{10}^{*}$$	=	$$\set$$1, 3, 7, 9
$$\varphi$$(11)	=	10	since	$$\Z_{11}^{*}$$	=	$$\set$$1, 2, 3, 4, 5, 6, 7, 8, 9, 10
$$\varphi$$(12)	=	4	since	$$\Z_{12}^{*}$$	=	$$\set$$1, 5, 7, 11

Of course, Maple also knows about the function $\varphi$ 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 $\varphi$.

(a) This is immediate, since all non-zero elements of $\set$0, 1,..., p-1 are invertible.

(b) We prove this part just by counting. Since p is prime, the only numbers in $\Z_{p}^{}$ which are not relatively prime to pⁿ are multiples of p. These are 0, p, 2p, 3p,..., p²,(p + 1)p,...,(p^{n - 1} - 1)p. Note that p^{n - 1}p = pⁿ, so there are exactly p^{n - 1} multiples of p less than pⁿ (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 $\Z_{ab}^{*}$ is the same as the product of the size of $\Z_{a}^{*}$ and $\Z_{b}^{*}$. We do that by showing that for each t $\in$ $\Z_{ab}^{*}$, there is exactly one pair (r, s) with r $\in$ $\Z_{a}^{*}$ and s $\in$ $\Z_{b}^{*}$.

So, let r $\in$ $\Z_{a}^{*}$ and s $\in$ $\Z_{b}^{*}$. Then, by the Chinese Remainder Theorem (Thm. 10.5), there is an integer t < ab with

t $$\equiv$$ r mod a        and        t $$\equiv$$ s mod b.

Since t is a solution of the first, we can find an integer k so that r = t + ka, so gcd(t, a) = gcd(a, r) = 1 by Lemma 10.3. Similarly, gcd(t, b) = 1. Since t is relatively prime to both a and b, it is relatively prime to their product, so gcd(t, ab) = 1. Thus t $\in$ $\Z_{ab}^{*}$.

Now take t $\in$ $\Z_{ab}^{*}$, and we must find a corresponding r and s. Let r = $\modn$ta. Now, since gcd(t, ab) = 1, certainly gcd(t, a) = 1. Since r $\equiv$ t mod a, there is an integer k so that t = r + ka, so we have gcd(r, a) = 1. Thus r $\in$ $\Z_{a}^{*}$. Similarly, we let s = $\modn$tb, and we see that s $\in$ $\Z_{b}^{*}$.

Since we have paired each t $\in$ $\Z_{ab}^{*}$ with a unique pair (r, s) $\in$ $\Z_{a}^{*}$×Z_b^*, they have the same cardinality. The first set has $\varphi$(ab) elements, and the latter has $\varphi$(a)$\varphi$(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

a$$\Z_{n}^{*}$$ = $$\set$$$$\modn$$abn$$\st$$b $$\in$$ $$\Z_{n}^{*}$$.

Since a and n are relatively prime, $\modn$an $\in$ $\Z_{n}^{*}$. Thus every element of a$\Z_{n}^{*}$ is in $\Z_{n}^{*}$. But also every element of $\Z_{n}^{*}$ is an element of a$\Z_{n}^{*}$, since $\modn$abn = $\modn$acn if and only if $\modn$bn = $\modn$cn. This means that the sets a$\Z_{n}^{*}$ and $\Z_{n}^{*}$ are equal.

Now, multiply all the elements of $\Z_{n}^{*}$ together; call the result N. Then $\modn$Nn $\in$ $\Z_{n}^{*}$. If we multiply all the elements of a$\Z_{n}^{*}$ together, we get a^$\varphi$(n)N, and since the two sets are the same, we have

$$\modn$$a^$\varphi$(n)Nn = $$\modn$$Nn.

Thus,

$$\modn$$a^$\varphi$(n)n = 1.

Footnotes

... $$\varphi$$ - function,^4.31

Although the function was invented by Euler, the notation $&phiv#varphi;(n)$ to represent it is actually due to Gauss.