CIS 675: Algorthms – Spring 2019
Homework 2

Version 3 (29 January 2019)

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.

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: $O($ some polnomial in $m$ and $n)$ . Remember to justify your answer.
(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)
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$ .
(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 $p$ is prime and $1\leq a <p$ . 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)$ .