Math 187A (Fall 2025)

October 31: 

October 29: Quiz 3.

October 27: We learnt how to perform the G-test with an example (see textbook Section 3.7) and how to decipher a ciphertext which was encrypted using rectangular transposition using the G-test.

October 24: We described how to break the Vignere cipher. The key idea we introduced was the Index of coincidence for an English text. The Index of Coincidence is defined in the textbook and it can be approximated by 26 (p_A^2 + p_B^2 + … + p_Z^2) where p_A = (# of times A occurs in the text/(total # of letters in the text), and similarly for p_\alpha for other \alpha. While the Index of coincidence can be as large as 26, for (large) plaintext from the English language, this is almost always between 1.5 and 2, and very often 1.75 ± 0.1. Now, to break the Vignere cipher, we first guess the period p and break the ciphertext into p columns and compute IC of each column. If the IC’s of all columns are ~1.75, we can assume we have guessed the period correctly, and then guess the shifts of each column via a Frequency analysis as we did on October 15. If the IC’s of all columns are not close to 1.75, we change the period and try again…

October 20: Introduced probability spaces, random variables, and conditional probability. Reading homework from last week is only due October 21 by noon via the usual form, and another Reading Homework is due October 22 by midnight (read first three sections of Chapter on Codebreaking and solve Exercises 3.3.5, 3.3.12, 3.3.13, 3.3.14) via new Google Form.

October 17: Quiz 2. Reading Assignment for October 20: Exercise 3.2.4, 3.2.5, 3.2.6, and 3.2.7 (Google Form has been updated).

October 15: We did another Hill Cipher example and moved to Codebreaking, which is the point of view of Eve rather than Alice and Bob. We talked about Frequency Analysis which allows us to easily break any simple substitution ciphers. We fumbled through one example (opening passage of "A tale of two cities") using the Sage cell in the textbook. Please try the last example from Section 3.2. The reading assignment from Oct 13 is only due tomorrow at 9am.

October 13: We saw that if the encryption function E(x) = a x + b and r is an inverse of a mod 26, then the Decryption function is D(y) = ry - rb. We also saw that the number of different Affine ciphers is 12*26. We then talked about 2 x 2 matrices, when they are invertible mod 26, and how to compute their inverse. Using this, we defined the Hill Cipher, the key for which is an invertible 2 x 2 matrix. The reading assignment is slightly different and is only due October 16, 9am.

October 10: We deduced the modular inversion theorem: a is invertible mod n if and only if gcd(a, n) = 1; in this case, the inverse of a is a Bezout coefficient for a in the identity "r a + s n = 1". This allows us to generalize the Caesar cipher in another way, which is called an Affine cipher. The Caesar cipher can be thought of as applying the transformation E(x) = x + b mod 26, where b is the shift. For an affine cipher, we can do any linear transformation E(x) = ax + b mod 26, as long as this function is invertible (so that the ciphertext is decipherable). By the modular inversion theorem, this is possible if and only if gcd(a, 26) = 1. 

October 08: We defined the greatest common divisor of two integers and noted that gcd(a, 0) = a for a nonzero positive, and gcd(bq+r, b) = gcd(b, r). These two observations immediately lead to the Euclidean algorithm. The reason why we care about the Euclidean algorithm is not necessarily to compute the gcd but rather that we immediately obtain Bezout's identity: for any integers m and n, there exists integers r and s such that gcd(m, n) = r m + s n; the coefficients r and s here are called Bezout coefficients. We did many examples in class. 

October 06: Quiz 1

October 03: We finally introduced modular arithmetic and the key identitites: a ≡ a' (mod n) and b ≡ b' (mod n) implies a + a' ≡ b + b' (mod n) and aa' ≡ bb' (mod n). We then recast the Caesar cipher using modular arithmetic (encrypting is just adding the shift mod 26 and decrypting is just subtracting the shift mod 26). This quickly allows us to come up with the Vigenère cipher which requires a KEY word: this is a ``periodic" Caesar cipher where the period is determined by the length of keyword and the shift is determined by the letters of the keyword.  Reflection Assignment 1 is up and is due on October 10.

October 01: We started with a few examples of the Playfair cipher in detail. Explained how to obtain the 5x5 grid used in Playfair cipher from a keyword. Spent some time discussing certain conventional issues that come up in Rectangular transposition, and while encoding the phrase for Playfair cipher. [For the most part, we will stick to the textbook; attempt many examples with the Sage cells to sus out possible edge cases like BOX]. Reading assignment: sections on "Overview of Classical Cryptosystems", "Rectangular transposition", and "Masonic cipher". Reading assignments are due by noon on the day of the next non-quiz class day. 

September 29: Saw the following substitution ciphers:  Caesar Cipher, Simple Substitution cipher, and Polybius Square (ADFGVX cipher). Saw a short example of using the Playfair cipher. Read Chapter 1 from the textbook for Reading Assignment and fill the google form before noon on Oct 1. The first quiz is on October 06.

September 26: Quick history of cryptography. Saw how to use Rectangular transposition