The Mathematics of Public-Key Cryptography, Assignment 2

due 11:30 AM, October 19, 2000

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?
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.
3. Suppose that n=317940011 and b=77537081 in the RSA Cryptosystem. Using Wiener's algorithm, attempt to factor 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.
5. Suppose throughout this question that p is prime and gcd(a,p) = 1.
   1. Suppose 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.
   2. 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.
   3. For all i >= 1, prove that the number of solutions to the congruence x^2 = a mod p^i is either 0 or 2.
6. Suppose p = 199, q = 211 and B = 1357 in the Rabin Cryptosystem. Perform the following computations.
   1. Determine the four square roots of 1 modulo n, where n = pq.
   2. Compute the encryption y = e_K(32767).
   3. Determine the four possible decryptions of this given ciphertext y.