The Mathematics of Public-Key Cryptography, Assignment 5

due 11:30 AM, November 30, 2000

1. Do question 5.9 from the textbook.
2. Do question 6.1 from the textbook.
3. Let L_i denote the set of positive integers that have exactly i coefficients in their NAF representation, such that the leading coefficient is 1. Denote k_i = |L_i|.
   1. By means of a suitable decomposition of L_i, prove that the k_i's satisfy the following recurrence relation: k_1 = k_2 = 1; k_{i+1} = 2(k_1 + k_2 + ... + k_{i-1})+1 (for i >= 2).
   2. Derive a second degree recurrence relation for the k_i's, and obtain an explicit solution of the recurrence relation.
4. Prove that every positive integer has exactly one NAF representation. (Note: we showed in class that every integer has at least one NAF representation, so it suffices to prove that the NAF representation is unique.)