CIS 675: Algorthms – Spring 2019
Homework 2

Version 3   (29 January 2019)




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