Mathematics for Computer Science

Chapter 8 Number Theory310

Problem 8.73. (a)Show that ifpjnfor some primepand integern > 0, then
.p1/j.n/.

(b)Conclude that.n/is even for alln > 2.

Problem 8.74. (a)Calculate the value of.6042/.

Hint: 53 is a factor of 6042.

(b)Consider an integerk > 0that is relatively prime to 6042. Explain why
k^9361 k .mod6042/.

Hint:Use your solution to part (a).

Problems for Section 8.11

Practice Problems

Problem 8.75.
Suppose a cracker knew how to factor the RSA modulusninto the product of
distinct primespandq. Explain how the cracker could use the public key-pair
.e;n/to find a private key-pair.d;n/that would allow him to read any message
encrypted with the public key.

Problem 8.76.
Suppose the RSA modulusnDpqis the product of distinct 200 digit primespand
q. A messagem 2 Œ0::n/is calleddangerousif gcd.m;n/Dp, because such anm
can be used to factornand so crack RSA. Circle the best estimate of the fraction
of messages inŒ0::n/that are dangerous.

1

200

1

400

1

20010

1

10200

1

40010

1

10400

Problem 8.77.
Using the RSA encryption system,Pete thepublisher generates a private key.d;n/
and posts a public key,.e;n/, which anyone can use to send encrypted messages to
Pete.
RSA has the useful property that these same keys can switch roles: if Pete wants
to broadcast an unforgeable “signed” message, he can encrypt his message using