Assignment 2 Solutions

1.  Factor 262063, 9420457 and 181937053 using the Pollard rho algorithm, 
if the function f is defined to be f(x) = x^2+1. 
How many iterations are need to factor each of these three integers? 

     n = 262063
     x_{35} = 225384, x_{70} = 94604, 
     gcd(225384 - 94604, 262063) = 503
     n = 503 * 521 
 
     n = 9420457
     x_{50} = 4559325, x_{100} = 6376648, 
     gcd(4559325 - 6376648, 262063) = 2351
     n = 2351 * 4007

     n = 181937053
     x_{165} = 2452153, x_{330} = 73737576, 
     gcd(2452153 - 73737576, 181937053) = 12391
     n = 12391 * 14683
 
2.  Suppose we want to factor the integer n = 256961. 
Using the factor base {-1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}, test
the integers z^2 mod n for z = 500, 501, ... , 
until a congruence of the form x^2 = y^2 mod n is obtained and the
factorization of n is found. 
          
     503^2 mod n = (-1) * 2^4 * 13 * 19
     504^2 mod n = (-1) * 5 * 19 * 31
     505^2 mod n = (-1) * 2^4 * 11^2
     507^2 mod n = 2^3 * 11
     511^2 mod n = 2^6 * 5 * 13
     516^2 mod n = 5 * 11 * 13^2
     519^2 mod n = 2^4 * 5^2 * 31
     
     The first dependence relation is:
     
     (503 * 504 * 511 * 519)^2 = 
     (2^7 * 5^2 * 13 * 19 * 31)^2 mod n
     
     75319^2 = 91105^2 mod n
     
     gcd(75319 + 91105, n) = 293
     gcd(75319 - 91105, n) = 877
     
3.  Suppose that n=317940011 and b=77537081 in the RSA Cryptosystem. 
Using Wiener's algorithm, attempt to factor n.

     The continued fraction expansion of b/n is
     [0, 4, 9, 1, 19, 1, 1, 15, 3, 2, 3, 71, 3, 2]
     The fourth convergent is 10/41.
     Then (41*b - 1)/ 10 = 317902032.
     The quadratic equation x^2 - 37980x + 317940011 = 0
     has roots 12457 and 25523.  These are the factors of n.

4.  If q_1, ... q_m is the sequence of quotients obtained 
in the applying the Euclidean algorithm with input r_0, r_1, prove
that the continued fraction [q_1, ..., q_m] = r_0 / r_1. 
     
     Proof:  From the Euclidean Algorithm, we have
     
                     r_0 = q_1r_1 + r_2
                     r_1 = q_2r_2 + r_3
                     ...
                     r_{m-1} = q_mr_m 
             
             We prove by reverse induction on j that
             [q_j, ..., q_m] = r_{j-1} / r_j
             for 1 <= j <= m.
             
             The base case is j=m, where
             [q_m] = q_m = r_{m-1} / r_m.
             
             Assume the formula is true for j=i+1, and
             then prove it is true for j=i.
             From the Euclidean Algorithm, we have
             
                     r_{j-1} = q_jr_j + r_{j+1}
             so
                     r_{j-1}/ r_j  = q_j + r_{j+1} / r_j
                                   = q_j + 1/ (r_j / r_{j+1})
                                   = q_j + 1/ [q_{j+1}, ..., q_m] (by induction)
                                   = [q_j, q_{j+1}, ..., q_m] 
             
             By induction, the result is true for 1 <= j <= m. 
             Setting j=1, we see that   
                    
                     r_0/ r_1 = [q_1, ..., q_m], 
             
             as desired.
             
5.  Suppose throughout this question that p is an odd prime and gcd(a,p) = 1. 
(a) Suppose i >= 2 and b^2 = a mod p^{i-1}. Prove that there is a unique 
x in Z_{p^i} such that x^2 = a mod p^i and x = b mod p^{i-1}. 
Describe how this x can be computed efficiently. 

  Since b^2 = a mod p^{i-1}, we have that b^2 - a = K * p^{i-1} 
  for some integer K. Since x = b mod p^{i-1}, we can write
  x = L * p^{i-1} + b for some integer L. Now we compute x^2 mod p^i:
  x^2 = (L * p^{i-1} + b)^2 = L^2 * p^{2i-2} + 2bL * p^{i-1} + b^2
  = L^2 * p^{2i-2} + 2bL * p^{i-1} + K * p^{i-1} + a
  x^2 mod p^i = p^{i-1} (2bL + K) + a,
  so x^2 = b mod p^i if and only if 2bL + K = 0 mod p.
  This is true iff L = -K * (2b)^(-1) mod p.
   
(b) Illustrate your method in the following situation: 
starting with the congruence 6^2 = 17 mod 19, find square
roots of 17 modulo 19^2 and modulo 19^3. 

  6^2 - 17 = 1 * 19, so K = 1
  Then L = -1 * 12^(-1) mod 19 = -1 * 8 mod 19 = 11,
  so x = 11*19 + 6 = 215 mod 361
  
  Next, 215^2 - 17 = 128 * 361, so K = 128
  Then L = -128 * 8 mod 19 = 2 
  (there is no need to recalculate (2b)^(-1) mod p),
  so x = 2*361 + 215 mod 19^3 = 937 mod 19^3

(c) For all i >= 1, prove that the number of solutions to the 
congruence x^2 = a mod p^i is either 0 or 2.   

  The proof is by induction on i. For i=1, x^2 = a mod p
  has no solutions or 2 solutions, depending on the Legendre
  symbol a mod p. The result proved in part (a) establishes
  that the number of solutions modulo p^i is the same 
  as the number of solutions modulo p^(i-1) for all i >= 2.
  
6.  Suppose p = 199, q = 211 and B = 1357 in the Rabin Cryptosystem. 
Perform the following computations. 
(a) Determine the four square roots of 1 modulo n, where n = pq. 

    n = 41989
    If x = 1 mod 199 and  x = 1 mod 211, then x = 1 mod 41989
    If x = -1 mod 199 and  x = -1 mod 211, then x = -1 mod 41989
    If x = 1 mod 199 and  x = -1 mod 211, then x = 35025 mod 41989
    (using the Chinese remainder theorem).
    If x = -1 mod 199 and  x = 1 mod 211, then x = -35025 mod 41989 = 6964.
    
(b) Compute the encryption y = e_K(32767). 

    32767(32767 + 1357) mod 41989 = 16027
    
(c) Determine the four possible decryptions of this given ciphertext y.    

    B/2 mod n = 21673
    B^2/4 mod n = 29975
    The decryptions are x = sqrt(4013) - 21673
    To find one square root, compute
    4013^((p+1)/4) mod p = 86
    and 4013^((q+1)/4) mod q = 209,
    and then use the CRT to get 
    sqrt(4013) = 29538 mod n.
    The other square roots are obtained by multiplying
    this square root by the four square roots of 1 mod n, yielding
    29538, 12451, 1479, 40510.
    The four decryptions are 
    7865, 32767, 21795, 18837.