# CIS 675: Algorthms – Spring 2019 Homework 2

Abbreviations

• DPV = Algorithms, by S. Dasgupta, C. Papadimitriou, and U. Vazirani, McGraw-Hill, 2007.
• PG = Problems on Algorithms, 2/e, by Ian Parberry and William Gasarch.

• Chapters 1 and 2 of DPV

#### Problems

You many make use of the rsa.hs code to help with calculations.

1. (10 points) DPV Problem 1.7
Note: I am looking for an answer of the form: some polnomial in and . Remember to justify your answer.

2. (10 points) DPV Problem 1.10
Hint: Recall that means that for some integer .

1. (10 points) Suppose is prime, , , and .
Show that .
2. (10 points) Use part a to compute: .           (Corrected)
3. DPV Problem 1.19. Do this problem in two parts: XXX
1. (10 points) Show that, for any 1, .           (Corrected)

2. (10 points) Use a and Euclid’s rule to show that, for each , .

4. (10 points) DPV Problem 1.20. Show your computations for these.
Hint: See the last page of the "Arithmetic Algorithms, Part 1 slides.

5. (10 points) DPV Problem 1.27

#### Reference

• Fermat’s Little Lemma:
Suppose is prime and . Then .

• Euler’s Corollary (of Euler’s Theorem):
Suppose and are primes with and .
Then .

• Euclid’s Rule:
Suppose . Then .