CS 688: Computational Arithmetic-Geometry and Applications

We want to count the number of roots of an algebraic system (over finite fields). This is a very difficult question in general (eg. #P-hard). However, there are fast algorithms known for special cases. In this course we will focus on the "2-variable" case, i.e. curves. This case already demands significant theory and has an amazing list of applications in computer science. We will cover some important aspects of the theory in a self-contained way, and see as many applications as time permits. .

- Algebraic-geometry notation
- Zeta function of curves over finite fields
- The relevant Riemann hypothesis
- Finally, its proof and Weil bound for curves

- Counting points on curves
- Integer factoring via curves 
- Hyperelliptic curve cryptography
- Algebraic geometry codes
- Computing roots of unity in finite fields

o Assorted lecture notes and books.
o Carlos Moreno, Algebraic curves over finite fields, Cambridge Tracts in Mathematics, vol. 97, Cambridge University Press, 1991.
o http://home.imf.au.dk/shave/dvi_files/Zeta.pdf