Mathematics for Computer Science

Chapter 8 Number Theory214

(a) Ifpis a prime, then.pk/Dpkpk^1 fork 1.

(b) Ifaandbare relatively prime, then.ab/D.a/.b/.

Here’s an example of using Theorem 8.7.6 to compute.300/:

.300/D.2^2 
 3 
 52 /

D.2^2 /
.3/
.5^2 / (by Theorem 8.7.6.(a))

D.2^2  21 /.3^1  30 /.5^2  51 / (by Theorem 8.7.6.(b))

D80:

To prove Theorem 8.7.6.(a), notice that everypth number among thepknumbers

inŒ0;pk/is divisible byp, and only these are divisible byp. So1=pof these

numbers are divisible bypand the remaining ones are not. That is,

.pk/Dpk.1=p/pkDpkpk^1 :

We’ll leave a proof of Theorem 8.7.6.(b) to Problem 8.18.

As a consequence of Theorem 8.7.6, we have

Corollary 8.7.7. For any numbern, ifp 1 ,p 2 ,... ,pj are the (distinct) prime

factors ofn, then

.n/Dn



1

1

p 1



1

1

p 2





1

1

pj



:

We’ll give another proof of Corollary 8.7.7 in a few weeks based on rules for

counting.

8.8 The RSA Algorithm

Finally, we are ready to see how theRSA public key encryption schemeworks. The

details are in the box on the next page.

It is not immediately clear from the description of the RSA cryptosystem that the

decoding of the encrypted message is, in fact, the original unencrypted message.

We’ll work that out in class.

Is it hard for someone without the secret key to decrypt the message? No one

knows for sure but it is generally believed that ifnis a very large number (say,

with a thousand digits), then it is difficult to reverse engineerdfromeandn. Of

course, it is easy to computedif you knowpandq—do it the same way the