CS 538 - Homework 4

                    CS 538 - Assignment #4



Date Due:  Tuesday, March 30

Reading:  Chapters 6 and 7,  pages 202-246

Problems:


1.  a. How many number are there with 5 or less digits. 

b. Assuming the prime number theorem is accurate for numbers of this size,
about how many primes  are there with 5 or less digits ?
(You can find the prime number theorem on page 129 of the text.)

c. Assuming that we choose an ODD  5 digit number at random, what is
the probability that it is prime ? 

2. Use the fast exponentiation algorithm to compute 
5^81  mod 14. Show your work.

3. Page 161, #4.18

4. Consider equation 4.1 on page 144 of the text.

a. For y = 96, show how you can compute half(y) using parity (y).

b. Prove equation 4.1 is true for any y.

5. Assume we have a probabilistic primality testing algorithm which
works as follows on input x. The algorithm always answers yes or no.
If x is prime, on input x the 
algorithm always answers yes. If x is not prime then the probability 
that it answers no is 1/2. 

Explain how you could use this algorithm to determine, with probability
.9999,  if a number is prime.

Assuming that one run of the algorithm takes 10 seconds, how long 
would this take (at most) ?


Do either one of the following 2 problems:

6a. Page 158, #4.6 (Only do the ciphertext in table 4.2)

6b.  Page 158, #4.7