Previous lecture
Table of contents
Next lecture

Lecture #12:  Fermat's little theorem

I asked people to do the Diffie-Hellman homework problem and did get some volunteers. I even awarded a prize. Note that some methods of working with the problems yield a complaint by Maple saying "Error, object too large" (an outcome expected by me). Therefore computations must be done in an intelligent order.

Then I wrote the multiplication table mod 7, looked at the rows and multiplied the non-zero rows. I deduced a version of Fermat's little theorem (1640) even for really large primes. The row products (away from the 0 edge) are always the same, and the row products are all ap-1 times each other, so that ap-1=1 mod p when p is a prime. This went very slowly, and there was great confusion about the algebra of exponents.

Then I recited Euler's generalization (1760) of the Fermat result, when the base of the modulus is the product to two different odd primes. I also recited Hardy's dictum about number theory being not too useful and observed that the "real world" was actually strongly contradicting his assertion. Last semester I had rushed through the proof of Fermat's theorem, and stated Euler's generalization, and then applied it all immediately to produce RSA. This was too much material too fast, and the result was a shambles. I resolved to proceed more slowly this time.

Mr. Radomirovic wrote some very nice material about RSA. I gave out his introductory pages [PDF|PS|TeX] and the students and I worked through the first two problems.

I reminded people that they could go to a presentation by Matt Blaze. In fact, my e-mail message about this was as follows:

Matt Blaze wrote the pointed and amusing essay, "My Life as an International Arms Courier" (see if you've never read it). He works on cryptography and computer security at AT&T. He has advised the U.S. government and worked with various less official groups about the policy implications of crypto and computer security regulations. His web site is and he will be giving a talk at Rutgers on
Tuesday, February 29, 2000 at 7 PM
in the CORE Auditorium on Busch campus.
The topic of the talk is
Loaning Your Soul to the Devil:
A Scientist's Perspective on Secrecy, Spies,
Cryptography, and Washington
and it should be very interesting: a nice way to commemorate February 29, '00 (only one every four hundred years). A reception will follow.

I had previously given students a copy of Blaze's essay. A number of the students did attend, and the presentation, about some of the public policy aspects of crypto, seemed to be quite well-received. The auditorium was full (some people were standing) and attendance seemed to be spread among faculty, graduate and undergraduate students, and other members of the community.

Previous lecture
Table of contents
Next lecture