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