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 as
exp 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 and
crt -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 261-1, g is 23489. The
secret numbers SA and B are 10480
and 15011. (8 pts.)
- (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.,
xy mod n = xy mod phi(n) mod n.
(10 pts.)
Last updated
by Henning Schulzrinne