Math 187A (Winter 2026) [ARCHIVE]

March 13: Makeup quiz

March 11: Quiz 5 Note: If you might miss Quiz 5, you must email me by Monday (03/09) midnight

March 9: We discussed how the Elliptic curve Elgamal algorithm is implemented. [Section 4.13]

March 6: We saw how to find the order of a^d modulo n provided we know the order of a modulo n -- it is just ord_n(a)/(gcd(d, ord_n(a)). We finally defined the notion of a quadratic residue -- an integer a is a quadratic residue modulo n if a is a square modulo n, i.e., there exists x such that x^2 ≡ a (mod n). For an odd prime p, we introduced the Legendre symbol (a/p) which is defined to be 0 if p divides a, +1 if p does not divide a and a is a quadratic residue mod p, and -1 otherwise. We computed some values and proved Euler's criterion: (a/p) ≡ a^{(p-1)/2} mod p. [Section 4.12]

March 4: We saw the Elliptic Curve Diffie--Hellman algorithm -- this is very similar to the ordinary Diffie--Hellman algorithm, except the public key is (E, p, P) where E is an elliptic curve which is nonsingular modulo p, and P is a solution of E modulo p; and rather than exponentiating an integer modulo p, both Alice and Bob, after choosing secret keys k_a and k_b, instead compute and share k_a P and k_b P respectively; and the shared message is just the point k_a k_b P on E modulo P. [Section 4.11]

March 2: We first defined the notion of an order of a point P on an elliptic curve E -- it is the smallest r > 0, if it exists, such that rP = O. We noted that for an elliptic curve over the real numbers, very few points have finite order. An elliptic curve E with a and b integers is nonsingular modulo p if its Discriminant is not divisible by p. Fixing such a p, we discussed the solutions of E modulo p; the solutions of E modulo p along with the point at infinity can also be endowed with an addition operation. Since the number of solutions modulo p is at most p^2, all points on E modulo P have finite order, denoted ord_{E, p}(P). Furthermore, if rP = 0, then ord_{E,p}(P) divides r. The Discrete Logarithm Problem for Elliptic Curves is the following: given a prime p and an elliptic curve E which is nonsingular mod p, and points P and Q on E mod p, if Q = rP, can you compute r? This problem is computationally hard and forms the basis of most Elliptic curve cryptographic algorithms. [Section 4.9; 4.10]

February 27: After doing an explicit example with the Elgamal encryption system, we defined an Elliptic curve. For us, an elliptic curve E is, for fixed a and b with -16(4a^3 + 27b^2) ≠ 0, the points on the x-y plane defined by the equation y^2 = x^3 + ax + b along with the point at infinity. We are interested in elliptic curves as we can use the geometry of an elliptic curve to define an addition operation on its points. To compute P+Q, we first draw the secant line joining P and Q; this line meets the curve at a third point reflect this point along x-axis, and P+Q is the reflection of this third point along the x-axis. To compute P+P, we draw the tangent line to E at P and reflect the second point of intersection along the x-axis. For example, consider the Elliptic curve defined by y^2 = x^3 + 1; the points P=(-1,0) and Q = (0,1) are on E, and doing this process yields P+Q = (2, -3). [Section 4.8, 4.9]

February 25: Quiz 4

February 23: We introduced order of an integer a modulo n where gcd(a, n) = 1: it is the smallest positive integer r such that a^r ≡ 1 (mod n). We saw that ord_n(a) divides phi(n). An integer a is a primitive root modulo n if order ord_n(a) = phi(n). Modulo n, a primitive root need not exist, but if n is a prime, a primitive root always exists, i.e., if p is a prime, there exists a g not divisible by p such that g^{p-1} ≡ 1 (mod p) and g^i is not equivalent to 1 (mod p) for 0 < i < p-1. Furthermore, the integers g, g^2, g^3, ..., g^{p-1} are all pairwise unequal modulo p, so that means for each integer j in {1, 2, ..., p-1}, there exists a unique integer i in {1, 2, ..., p-1} such that g^i ≡ j (mod p). We set the integer i<p to be the discrete logarithm log_g (j mod p). Given a primitive root g modulo p, computing the discrete logarithm is in general a hard problem. [Section 4.6]

February 20: We implemented the RSA algorithm: BOB chooses a large number n = pq, where p and q are two large distinct primes, and also a number d which is coprime to phi(n) = (p-1)(q-1). BOB computes a multiplicative inverse of d mod phi(n), call it e. The pair (n, e) are made public; p, q can be forgotten, and d is kept private. If ALICE wants to send a message m, she computes c = m^e mod phi(n) and sends c to BOB, who simply computes c^d, which we saw recovers m. The RSA algorithm is secure because we believe computing prime factorizations is difficult (see Wikipedia page). [Section 4.5]

February 18: We first deduced several formulas for the Euler totient function (especially phi(n) = n \prod_{p divides n} (1 - 1/p) ) from the fact that it is multiplicative. We then saw Euler's theorem: given coprime integers a and n, a^{phi(n)} ≡ 1 (mod n). This allows us to greatly speed up computing exponents modulo n. Specifically, we have a^N ≡ a^r (mod n) where N ≡ r (mod phi(n)). [Section 4.3]

February 13: We learnt how to compute binary expansions for integers, the remaining step in binary exponentiation. We then defined the Euler totient function and stated the fact that it is a multiplicative function. [Section 4.3, 4.2]

February 11: Quiz 3

February 09: I explained how Diffie--Hellman key exchange works, and why working in real numbers allows Eve to easily break it using the analytic logarithm. We then quickly computed exponents using binary exponentiation. [Section 4.8, 4.3]

February 06: Demonstrations with SageCells in the textbook. We started Chapter 4 [Section 3.8, 3.9, 4.1]

February 04: We saw how to implement a known-plaintext attack for any ciphertext that was encrypted using a simple substitution cipher [Section 3,8, 3.9].

February 02: We learnt how to perform the G-test with an example and how to decipher a ciphertext which was encrypted using rectangular transposition using the G-test. [Section 3.7, 3.8]

January 30: Quiz 2

January 28: 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… [Section 3.5, 3.6]

January 26: We started Chapter 3 and discussed how to use 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. [Section 3.1, 3.2]

January 23: We talked about 2x2 matrices and computing its determinant and inverses. Then we focussed on 2x2 matrices with entries in integers mod 26. In this case, a matrix is invertible if its determinant is coprime to 26. This allows us to construct the Hill Cipher, where the KEY is a 2 x 2 matrix which is invertible mod 26. [Section 2.10, 2.11]

January 21:We discussed how to use Bezout's coefficients to obtain (multiplicative) inverses of integers mod n. Specifically, if a and n are coprime, then ra ≡ 1 (mod n) where r is a Bezout coefficient of a in ra + sn = 1. This allowed us to construct Affine cipher. Specifically, we fix a and b integers where a is coprime to 26 which is the KEY. We use the standard letter-to-key correspondence to map each letter x to the letter corresponding to ax + b (mod 26). To decrypt a ciphertext, we map each letter y to r(y-b) mod 26, where r is an inverse of a mod 26. [Section 2.6, 2.7]

January 19: MLK Day. No class.

January 16: Quiz 1

January 14: We executed the Euclidean algorithm for many examples and saw how to obtain Bezout's theorem: given integers a and b, there exists integers r and s such that gcd(a, b) = r a + s b. The coefficients r and s are called Bezout coefficients of a and b respectively. [Section 2.6]

Jnauary 12: Explained how modular arithmetic works, and saw how to execute the Vigenere cipher. Defined the notion of the greatest common divisor of two integers. [Sections 2.5, 2.13]

January 09: Discussed Rectangular transposition and defined what it means for two integers to be equivalent mod n: a ≡ b (mod n) if and only if n divides (b-a), or equivalently, a and b leave the same remainder when divided by n. [Sections 2.2, 2.5]

January 07: Introduced Simple Substitution cipher, Polybius square (ADFGVX cipher), and Playfair cipher with many examples. [Sections 2.8, 2.9, 2.12]

January 05: Went through the Syllabus. Gave a quick history of cryptography. Saw how to execute Caesar cipher with an example. [Chapter 1, Section 2.4]

Lecture Time: MWF 11:00am to 11:50am
Lecture Location: Pepper Canyon Hall Room 106
Textbook: An Introduction to Cryptography, by Shishir Agrawal. Available online via this link.

Discussion Section:
Section A01: M 5:00pm-5:50pm at HSS 2321
Section A02: M 6:00pm-6:50pm at HSS 2321
Section A03: M 5:00pm-5:50pm at CENTR 203
Section A04: M 6:00pm-6:50pm at CENTR 203
Section A05: M 7:00pm-7:50pm at CENTR 203
Section A06: M 8:00pm-8:50pm at CENTR 203

Course Personnel:
Instructor: Karthik Ganapathy Venkitachalam
Teaching Assistant for Sections A01 and A02: Nathan Wenger
Teaching Assistant for Sections A03: Jasper Liu
Teaching Assistant for Sections A04: JD Flynn
Teaching Assistant for Sections A05 and A06: Jianxiang Tan
Note: To contact us, please use Piazza. The system is highly catered to getting you help fast and efficiently from classmates, the TA, and myself. Rather than emailing questions to the teaching staff, I encourage you to post your questions on Piazza. If you have a question that is fairly long, please come to office hours and speak to me directly.

Office Hours:
Karthik: WF 12:20pm to 1:50pm at AP&M 1230
Nathan:  M 2:30pm to 4:30pm HSS 5029
Jasper: W 9:30am to 10:30am at HSS 4070
JD: Tu 5-6pm in HSS 5086
Jianxiang: Th 1pm to 3pm at HSS 5053

Quizzes:
There will be five quizzes in class on the following dates: January 16, January 30, February 11, February 25, March 11 . Each quiz is cumulative but the emphasis will be what was covered the previous three or four lectures leading up to it. If you miss any of the five quizzes, you can take a makeup quiz on March 13. Aside from this, no makeup quizzes will be given. Each quiz is equally weighted.

Reading Assignments:
You will be assigned sections of the textbook to read every week, and you are expected to fill a form answering some basic questions based on these readings. Each reading assignment is equally weighted.

Reflection Assignments:
There will be three reflection assignments which will be posted on Canvas. They will be due on January 18, February 15, March 11. The first reflection assignment is worth 1% of your overall grade; the second and third are worth 2.5% each.

Final Exam:
It is on March 16 from 11:30am to 2:30pm in PCYNH 106. Cheat sheet policy is TBA. No makeup exams will be given in this course.
Note: It is standard Math Department practice to utilize different versions of exams, both within each lecture's exam, and between lectures whose exams are at different times.

Regrades: Regrade requests for Quizzes and the Final may be made using the built-in regrade request feature in Gradescope. Typically, you are given one week from when the scores are released to submit regrade requests. For the Final and later quizzes, this window will be greatly shortened.

Grading Policy:

To ensure fairness and recognize different paths to success, your final grade will be calculated using the highest score from three grading rubrics: 

1. 9% Reading Assignments; 6% Reflection Assignments; 45% Final; 40% Quizzes

2. 9% Reading Assignments; 6% Reflection Assignments; 35% Final; 50% Quizzes

3. 9% Reading Assignments; 6% Reflection Assignments; 60% Final; 25% Quizzes

The first rewards students who stay consistent with quizzes and assignments, the second protects against having a single off day during finals, and the third provides an opportunity to demonstrate mastery on the final exam even if earlier work was weaker. 

The final grades will be at least as generous as the standard ones (97.00 - 100.00 A+; 94.00 - 96.99 A; 90.00 - 93.99 A-; 87.00 - 89.99 B+; 84.00 - 86.99 B; 80.00 - 83.99 B-; 77.00 - 79.99 C+; 74.00 - 76.99 C; 70.00 - 73.99 C; <70.00 F)

Attendance Policy: You are expected to attend every session of the lectures and discussion section you are enrolled in. Students who do not attend class rarely succeed in this course.  If you must miss class for any reason, it is your responsibility to catch up on the material. You are also responsible for the information given in any announcements made during class. Please note that lectures will NOT be recorded.

Academic Integrity: Academic dishonesty is considered a serious offense at UCSD. Students caught cheating will face an administrative sanction which may include suspension or expulsion from the university. Using LLMs for any assignments will be considered a form of academic dishonesty. 

Accommodations: Students requesting accommodations for this course due to a disability must provide a current Authorization for Accommodation (AFA) letter issued by the Office for Students with Disabilities (https://osd.ucsd.edu/.) Students are required to discuss accommodation arrangements with instructors and OSD liaisons in the department in advance of any exams or assignments.

Food Support for Students: If you are skipping and stretching meals, or having difficulties affording or accessing food, you may be eligible for CalFresh, California’s Supplemental Nutrition Assistance Program, that can provide up to $298 a month on a debit card to buy food. Students can apply at benefitscal.com/r/ucsandiegocalfresh. And don’t forget to recertify every six months to continue receiving benefits.

The Hub Basic Needs Center empowers all students by connecting them to resources for food, stable housing and financial literacy. Visit their site at basicneeds.ucsd.edu.