## CS 688: Computational Arithmetic-Geometry and Applications

Contents:

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. .

Fundamentals:

- Algebraic-geometry notation

- Zeta function of curves over finite fields

- The relevant Riemann hypothesis

- Finally, its proof and Weil bound for curves

Applications:

- Counting points on curves

- Integer factoring via curves

- Hyperelliptic curve cryptography

- Algebraic geometry codes

- Computing roots of unity in finite fields

References:

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