This homework is due at
the beginning of class 19 on November 9, 2000. Note:
*K2.3* denotes homework problem 3 from chapter 2 of the class text.

- Write a C(++) or Java program that computes exponents efficiently,
using the mechanism described in the text. Your program should be able
to deal with base and exponents of up to 32 bits and modulo value of up to 32
bits. Make use of the
`long long`64-bit arithmetic found on most modern machines. Your program should take base, exponent and modulus as arguments, such asexp 45678 123 6789

Hints: use`strtoll()`for conversion from text to binary and`printf("%lu",...)`for printing. (16 pts.) - Write a C(++) or Java program that converts between composite and
common form, using the Chinese Remainder Theorem. Your program should
take the number(s) and modulus as pairs of inputs. I.e.,
crt -d 2 3 5

converts the number 2 in modulo (z1,z2) = (3,5) = 15 to decomposed representation andcrt -s 2 15 3 7 6 8

converts the number (2,15), (3,7), (6,8) to standard representation. Note: The two examples do*not*represent the same number. (16 pts.) - Using
`bc`, compute a shared key using Diffie-Hellman key exchange. Assume*p*is 2^{61}-1,*g*is 23489. The secret numbers*S*and_{A}are 10480 and 15011. (8 pts.)_{B} - (K5.2) In RSA, is it possible for more than one
*d*to work with a given*e*,*p*and*q*? (8 pts.) - (K5.3) In RSA, given that the primes
*p*and*q*are approximately the same size, approximately how big is*Ø(n)*compared to*n*? (7 pts.) - (K6.1) If
*m*and*n*are any two positive integers, show that*m/*gcd(*m,n*) and*n/*gcd(*m,n*) are relatively prime. [Hint: use the result of Euclid's algorithm.] (8 pts.) - (K6.2) If
*a*and*b*are relatively prime, and*bc*is a multiple of*a*, show that*c*is a multiple of*a*.*a*,*b*and*c*are in*Z*. [Hint: use the result of Euclid's algorithm.] (9 pts.) - (K6.7) For what type of number
*n*is*Ø(n)*largest (relative to*n*)? (7 pts.) - Implement Euclid's Algorithm in C(++) or Java. Output the
multiplicative inverse, the gcd and the linear representation of the gcd
(e.g., gcd(x,y) =
*ux + vy*). Test with the examples given in the book (p. 167 and p. 168). (20 pts.) - (Extra credit) Show that the relationship on pg. 133 holds, i.e.,
*x*. (10 pts.)^{y}mod n = x^{y mod phi(n)}mod n

Last updated by Henning Schulzrinne