You will work in groups of 1-3 on an expository paper showcasing an application of number theory/algebra to computer science. This will count for 30% of your grade, and will be graded on completion.
Instructions
One grading option for this course is 70% psets and 30% a short writeup (the other option being 100% psets). If you would like to pursue the writeup option, you will have to write a 2-3 page expository document about an application of algebra/number theory to CS by the end of the week. This should clearly explain (and give some proofs/justifications, when possible) the mathematics behind the application. If you plan to do this, please make a private piazza post with your proposal (topic, some details you plan to cover, and a source you’re following), and we will try to promptly respond.
The main goal for this is for you to learn some nice application and teach it to us.Example topics include the following ideas (which i’ve tried to sort) but feel free to propose anything you find interesting.
Discrete Logarithm and related topics:
-
Baby-steps Giant-Steps Algorithm
-
Index Calculus Method
-
Elliptic Curve Primality Testing
-
Pollard-rho algorithm
Cryptography:
-
Elliptic Curve Primality Testing
-
ElGamal Cryptosystem
-
Probabilistic Encryption & Goldwasser-Micali Cryptosystem
-
Lattice-based cryptography (Babai’s algorithm)
Group theory:
-
Cosets and Lagrange’s theorem
-
Primitive root diffuser (https://downloads.bbc.co.uk/rd/pubs/reports/1990-15.pdf)
-
Sylow’s theorems
-
Orbit-Stabilizer Theorem