Sections 3.4-3.5, due Monday, Oct 7

1. Having had experience with the Chinese Remainder thm, this part was relatively easy and a review for me. It might be worth it to memorize the formula for finding the solution for the simultaneous equivalences in terms of a and b, m and n. (Given ms + nt = 1, let x = bms + ant).
   
   The difficulty was actually in the section 3.5, modular exponentiation, specifically how they came up with the 2log_2(b) multiplications mod n.
   
   Why? The length of b written in binary is l = floor(log_2(b)) bits long, so we must calculate x^(2^l), which takes l squarings. If we store the results after each product, we have l values. The worst case is if b = (11111111...) in base 2. Then calculating x^b would take a product of all of these l values. This takes (l-1) products mod n.
   
   Thus there are at most 2l-1 which is about 2log_2(b).
   
   However, what is the approximate number of 1's in the binary form of a number b? We talked about worst case above. What is an "average" case?
   
   This is not a really well-defined question, I've found. Let f(n) be the number of ones in the binary expansion. It is unbounded, because f(2^k-1) = k, but does not tend to infinity, as f(2^k) = 1. So the question is really how to fit a curve to approximate this shape. My gut says c*log_2(b) is probably the answer. Eh~
   
2. The most interesting part of the reading tonight was what I just explained. It was all pretty familiar, as I said. In fact, I remember my 290 teacher from freshman year talking about modular exponentiation.