CS 812 - Arithmetic Algorithms
Notes for Lectures
W 1/24 - Course Intro
F 1/26 - School Arithmetic Complexity
M 1/29 - Asymptotic Arithmetic Complexity
W 1/31 - Greatest Common Divisor
F 2/2 - Congruences, Modular Arithmetic
M 2/5 - Exponentiation, Addition Chains
W 2/7 - Chinese Remainder Theorem
F 2/9 - Quadratic Residues
M 2/12 - Jacobi Symbols, Square Roots mod p
W 2/14 - Square Roots mod n
F 2/16 - The Density of Primes
M 2/19 - Short Certificates for Primes
W 2/21 - Randomized Prime Testing
F 2/23 - Small Circuits for Primality, Miller-Rabin Test
M 2/26 - Riemann Hypotheses and Algorithm Efficiency
W 2/28 - AKS Primality Test
F 3/1 - Correctness of AKS
M 3/4 - The Factorization Problem
W 3/6 - Factored Random Numbers
F 3/8 - Exponential Factoring Algorithms
M 3/11 - Dixon's Random Squares Algorithm
W 3/13 - Analysis for Random Squares
F 3/15 - The Quadratic Sieve
M 3/18 - Intro to the Number Field Sieve
W 3/20 - Baby-step / Giant-step Method
F 3/22 - Pollard's Kangaroo Method
M 4/1 - Logs in Zp in Subexponential Time
W 4/3 - Logs in fields of order 2^n
F 4/5 - Logs in fields of order 2^n (cont'd)
M 4/8 - Joux's Algorithm
W 4/10 - Dynamical Systems and Pseudo-Random Generators
F 4/12 - Iterated Affine Maps
M 4/15 - Predicting Lehmer Generators
W 4/17 - A Discrete-log Based Generator
F 4/19 - Projective Spaces, Secret Sharing
M 4/22 - Plane Curves
W 4/24 - Adding Points on an Elliptic Curve
F 4/26 - Factoring Integers with Elliptic Curves
M 4/29 - Elliptic Curve Point Counting
W 5/1 - Elliptic Curve Primality Tests
F 5/3 - Symbolic Integration