Lecture #5:  Modular arithmetic

I awarded the prize of a half pound of chocolates for the winners to the secret sharing assignment. I discussed the reasons for using Maple. Most students seem to have tried the problem, but not enough!

Then I asked what kind of arithmetic was needed for secret sharing. We needed exact arithmetic, to not lose information. Reality demands that arithmetic be rather fast. Also, the numbers shouldn't get too large because otherwise things would get unwieldy. I discussed the differences between fixed and floating point arithmetic -- some computer science majors who were present were able to help in this.

I introduced modular arithmetic, with the clock metaphor (past 12 o'clock, things cycle around again). This didn't seem to make things much easier (mod arithmetic had been introduced with some pains during the Fall semester incarnation of this course) I discussed arithmetic mod 9 in detail, constructing the addition and multiplication tables. I solved some linear equations mod 9. Some had unique solutions, some had several solutions, and some had none. Things seemed to go very slowly. This was not entirely a good class. It could have been done better.

Last semester I gave out reproductions of the specifications of secret sharing from Stinson's Cryptography book (pp. 326-331) which specifies secret sharing in a modular arithmetic environment. This seems to have been too difficult for most students. I think few people looked at this handout. Last semester I also handed out pp. 165-170 of Stephenson's novel, Cryptonomicon, which was an attempt to explain to his readers how modular arithmetic worked. Cryptonomicon is a treatment of many of the themes in the last half-century of cryptography, wrapped up in a long novel (900 pages).