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

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

(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.*(10 points) DPV Problem 1.10

**Hint:***Recall that means that for some integer .*- (10 points) Suppose is prime, , , and .

Show that . - (10 points) Use part a to compute: .
*(Corrected)*

- (10 points) Suppose is prime, , , and .
- DPV Problem 1.19. Do this problem in two parts: XXX
(10 points) Show that, for any

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

(10 points) DPV Problem 1.20. Show your computations for these.

**Hint:***See the last page of the "Arithmetic Algorithms, Part 1 slides.*(10 points) DPV Problem 1.27

**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 .