First Graduate Math Course

This is my first post as a graduate math student having completed my first course at Villanova University. Since I was eager to start I took an eight week summer course where each session was 3.5 hours long.

It was intense. The first homework assignment took between 15 and 20 hours to complete even though I skipped problems that were too hard or too time-consuming. Fortunately, the homework subsided in later sessions and even the sessions near the end of the term let out early.

We used what must be "the" book on the subject - Cryptography Theory and Practice by Douglas Stinson. The breadth of mathematics covered in the book (and we covered only about 20% of the book) is amazing. Linear algebra, abstract algebra, probability, and above all number theory. Euler considered number theory to be the queen of mathematics. It is certainly the linchpin of modern cryptography.

My favorite parts to this course were the programming assignments and the study of the RSA public key cryptosystem. I wrote the programs in Java 6 and learned new language features in the process. I'd estimate that I wrote about 1,000 lines of code. My teacher commented that I wrote "nice programs." Damn straight. I've been programming for over 35 years.

RSA public key stuff is fascinating because it's pure number theory. To study it you dip into many number theory topics including primality (this means "is it a prime number") testing and factorization of huge numbers. Now wonder Rivest, Shamir, and Adleman won the Turing Award in 2002. What I don't understand is why the El Gamal cryptosystem became the basis for the Digital Signature Algorithm standard instead of RSA. RSA is just as good for this and it means you have to purchase only one package for your business.

Another thing I don't understand is the theory behind the Index Calculus algorithm for computing discrete logarithms, namely the change in the modulus from p to p -1 as you go from (1) to (2) below.

(1) a^x_j º p₁^e_1j p₂^e_2j ... p_B^e_Bj (mod p)

(2) x_j º e_1j log_a(p₁) + ... + e_Bj log_a(p_B) (mod p-1)

Kind reader. If you can explain, please post a comment with the explanation. My teacher claimed that it was a direct result from Fermat's Little theorem, but I still don't see it.