# 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: $O($some polnomial in $m$ and $n)$. Remember to justify your answer.

2. (10 points) DPV Problem 1.10
Hint: Recall that $a \cong b \bmod N$ means that $(a-b)=k\cdot N$ for some integer $k$.

1. (10 points) Suppose $p$ is prime, $\gcd(a,p)=1$, $k\geq 0$, and $k'= (k\bmod (p-1))$.
Show that $a^k \cong a^{k'} \bmod p$.
2. (10 points) Use part a to compute: $2^{1678923} \bmod 137$.           (Corrected)
3. DPV Problem 1.19. Do this problem in two parts: XXX
1. (10 points) Show that, for any $n>$ 1, $F_{n+2} \bmod F_{n+1} = F_n$.           (Corrected)

2. (10 points) Use a and Euclid’s rule to show that, for each $n>0$, $\gcd(F_{n+1},F_n)=1$.

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 $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)$.