CS 812 - Arithmetic Algorithms

Instructor: Eric Bach

     Office : 4391 CS
     Phone : 262 7997
     E-mail : famous baroque composer at cs dot wisc dot edu
     Office Hours: MWF 11 (after class)

Handouts

• Course Description
• Course Topics
• Books on Reserve at College Library

Homework Assignments

• Homework 0 - questionnaire due Jan 20
• Homework 1 - due Feb 26 MacDuffee article
• Homework 2 - due Mar 20 Figure symmetry article
• Homework 3 - due Apr 29 Note by Campaigne
• Take-home Final - due May 10

What We've Covered

• See Here

Things to Read

• Blankinship on Euclid's Algorithm (Fri 2/2)
• Gordon on Exponentiation (Mon 2/5)
  
  
• Agarwal, Nitin, and Saxena on prime testing (Wed 2/28 -- Fri 3/1)
• Guerrier on Cyclotomic Polynomials mod p (Fri 3/1)
  
  
• Factored random numbers paper (Wed 3/6)
• Pollard on the ``rho'' method (Fri 3/8)
• Dixon on rigorous subexponential factoring (Mon 3/11 -- Wed 3/13)
• Koblitz on the quadratic sieve (Fri 3/15)
• Pollard on factoring F7 (Mon 3/18) and some notes on this
• Pomerance on QS and NFS (Mon 3/18)
  
  
• Pollard on the Kangaroo Method (Fri 3/22)
• Adleman on discrete log mod p (Mon 4/1)
• Coppersmith on logs in characteristic 2 (Wed 4/3, Fri 4/5)
• Joux and Pierrot on small-characteristic discrete logs (Mon 4/8)
  
  
• Papers on predicting Lehmer generators by Reeds and Plumstead (Mon 4/15)
• Blum and Micali on a pseudorandom generator based on discrete logs (Wed 4/17)
  
  
• Blakley on secret sharing (Fri 4/19)
• Lenstra on factoring with elliptic curves (Fri 4/26)
• Schoof on elliptic curve point counting (Mon 4/29) and some notes on this
• Goldwasser and Kilian on elliptic curve primality proofs (Wed 5/1)