# CIS 675: Algorthms – Spring 2019 Homework 3

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.

#### Problems

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

Notation: A[i..j] names the subarray A[i], A[i+1], … A[j].

1. (10 points) DPV Problem 1.33

2. (20 points) DPV Problem 1.36

3. (12 points) DPV Problem 1.45(b).

4. (36 points) DPV Problem 2.5, parts a, b, c, d, e, and i.

Obvious hint, use the [Master Theorem]. However, for part i, the Master Theorem will work; instead use a simple induction argument with $T(0) = 1$.

5. (10 points) DPV Problem 2.12

6. (12 points) PG Problem 337.

Hint: There is an infinite recursion that is possible.

#### Reference

• Fermat’s Little Lemma:
Suppose $p$ is prime and $1\leq a . Then $a^{p-1} \cong 1 \bmod p$.

• Euler’s Corollary (of Euler’s Theorem):
Suppose $p$ and $q$ are primes with $p\not=q$ and $\gcd(a,p\cdot q)=1$.
Then $a^{(p-1)(q-1)} \cong 1 \bmod (p\cdot q)$.

• Euclid’s Rule:
Suppose $x \geq y>0$. Then $\gcd(x, y) = \gcd(y, x \bmod y)$.

• Wikipedia on least common multiples

• Wikipedia on the Master Method