The final exam will cover the entire course but with greater emphasis
on the topics of lectures 12-24 that were not
covered by the midterm exam. The course content is presented in
several different formats:
In-person class lectures.
Written
lecture
notes, available on the course web site.
Written
handouts,
available on the course web site. I draw your attention to the four handouts on the more mathematical
aspects of the course:
Below I give a list of topics, concepts, definitions, theorems,
algorithms, and protocols that we have covered since the midterm that
I expect you to know. This list is not inclusive, as I'm sure I have
missed some things. Please refer to the
study
guide for midterm examination for the topics covered in the first
part of the course.
Number theory.
Primitive roots.
Lucas test.
Discrete logarithm.
Quadratic residues.
Square roots modulo a prime.
Square roots modulo a product of two distinct primes.
Euler criterion.
Finding square roots modulo prime p when p ≡ 3 mod 4.
Legendre symbol.
Jacobi symbol.
Jacobi symbol identities (don't memorize, but understand what they are).
Computing the Jacobi symbol.
Probabilistic primality testing
General framework for tests of compositeness (from
lecture notes 11).
Fermat test of compositeness ζ_{a}(n).
Strassen-Solovay test of compositeness ν_{a}(n)
Miller-Rabin test of compositeness μ_{a}(n).
Cryptographic protocols based on number theory (besides RSA).