Topics in Algebra and Computation

• Instructor : Chandan Saha   Course Level and No. of Credits : 300 and 3:1   Lecture time : M,W 11:30-13:00.


• Objective : Given the striking applications of algebraic methods in cryptography, coding theory and computational complexity theory, the aim of this course is to gain familiarity with some of the important and fundamental algebraic tools & techniques and see how these are applied effectively in the above-mentioned areas. The focus would be on theoretical aspects of `Computer Algebra' & the use of `Algebraic methods in theoretical computer science'.


• Syllabus : The course will consist of two parts - Part 1: Computational aspects of algebra & number theory (~18 lectures) Part 2: Use of algebraic methods in theoretical computer science (~10 lectures).
  
  Part 1 : We will study the tools Chinese remaindering, Discrete Fourier Transform, Resultant of polynomials, Hensel lifting, Automorphisms of rings, Short vectors in Lattices, Smooth numbers etc. - and see how these tools are used to design algorithms for certain fundamental problems like integer & polynomial factoring, integer & matrix multiplication, fast linear algebra, root finding, primality testing, discrete logarithm etc.
  
  Part 2: This will deal with certain applications of algebraic methods/algorithms in cryptography (RSA cryptosystem, Diffie-Hellman), coding theory (Reed-Solomon & Reed-Muller codes, locally decodable codes), introduction to analysis of boolean functions (Fourier analysis) and expander graphs.


• References : A. The books - "Modern Computer Algebra" by von zur Gathen and Gerhard, and "Introduction to Finite Fields", by Lidl & Niederreiter.
  B. Relevant research papers and online lecture notes.
  C. A similar course taught by the instructor at MPI.


• Prerequisites : Basic familiarity with linear algebra and properties of finite fields (as in the Chapter 1-3 of the book `Introduction to finite fields and their applications' by Rudolf Lidl and Harald Niederreiter). Alternatively, an undergraduate course in algebra. Most importantly, some mathematical maturity with an inclination towards theoretical computer science.


• Grading policy : Assignments - 40%; Mid-term exam - 30%; End-term exam - 30%


• Lecture notes : The following lecture notes are from a previous offering of a similar course at MPII, co-taught with Markus Bläser .
  • Lecture 1: Overview; RSA cryptosystem; Diffie-Hellman key exchange; Reed-Solomon codes
  • Lecture 2: Decoding of Reed-Solomon codes; Local decodablity
  • Lecture 3: Reed-Muller codes; Chinese Remaindering Theorem
  • Lecture 4: Fast Fourier Transform; Polynomial multiplication
  • Lecture 5: Integer multiplication; Polynomial division
  • Lecture 6: Multipoint evaluation, polynomial interpolation; Resultant
  • Lecture 7: Modular GCD computation; Polynomial factorization over finite fields
  • Lecture 8: Equal-degree factoring; Polynomial factoring to root finding; Testing irreducibility
  • Lecture 9: Generating irreducible polynomials; Miller-Rabin primality test
  • Lecture 10-11: AKS primality test ( paper )
  • Lecture 12: Hensel lifting; Bivariate polynomial factoring
  • Lecture 13: Hilbert's Irredicibility Theorem, Black-box polynomial factorization ( Madhu Sudan's lecture note )
  • Lecture 14: Sparse polynomial interpolation
  • Lecture 15: Short vectors in lattices; LLL basis reduction algorithm
  • Lecture 16: LLL basis reduction algorithm (contd.); Factoring polynomials over rationals
  • Lecture 17: Low exponent RSA; Pollard-Strassen integer factoring algorithm
  • Lecture 18: Pollard's rho method; Intro to smooth numbers
  • Lecture 19: Dixon's random square method
  • Lecture 20: The Quadratic Sieve method
  • Lecture 21: The index calculus method for computing discrete logatithm
  • Lecture 22-24: Complexity of bilear problems ( Markus Bläser's notes )
  • Lecture 25-30 : Expander graphs ( Hoory-Linial-Wigderson survery article )


• Assignments : Assignment 1 (due date: Feb 6, 2013), Assignment 2 (due date: Feb 28, 2013), Assignment 3 (due date: April 3, 2013), Assignment 4 (due date: April 24, 2013)


• Exams : Mid-sem (due date: Mar 18, 2013)