Introduction

Underneath many applications in real life like robotics, crytography, error correcting codes etc are certain basic computational tasks like gcd computation, factoring etc. This course is a study on such computational problems and the algorithms for them. We build on the necessary background from algebra and use it to give rigorous analysis of the performance of these algorithms.

Contents

The following topics will be covered in this course

  1. Basic algorithms for arithmetic, addition, multiplication and modular arithmetic. (4 lectures)

  2. Euclid's algorithm, Chinese Remainder theorem and applications to problems like determinant computation, Gaussian elimination. (6 lectures)

  3. Fields, Finite fields, Field of rationals, Polynomial factorisation over finite fields (6 lectures)

  4. Hensel lifting and application to bivariate factoring (4 lectures)

  5. Shortest vector problem and LLL algorithm. Application to factorisation of polynomial over rationals. (5 lectures)

  6. Applications of polynomial factorisation. (5 lectures)

  7. Multivariate system of polynomial equation and Grobner basis (7 lectures)

  8. Algorithms from number theory and cryptography (5 lectures).

Pre-requisites

None. The course will start from the very basics.

Learning Outcomes

  1. To state and analysis algorithms for tasks like arithmetic, factorisation.

  2. To apply the algorithms learned to tasks in cryptography, number theory etc.

Textbooks

  1. Modern Computer Algebra. Joachim von zur Gathen and Jurgen Gerhard. Cambridge University press, 2013. ISBN: 978-0521826464

References

  1. Algorithmic Algebra. Bhubaneswar Mishra. Springer 1993, ISBN-10: 0387940901, ISBN-13: 978-0387940908

  2. Ideal, Varities and Algorithms. David A. Cox, John Little, Donal O’Shea. Springer 2008. ISBN: 978-3-319-16721-3

  3. An Introduction to Grobner Bases. Philippe Loustaunau, William W. Adams. American Mathematical Society, 1994 ISBN-10: 0821838040, ISBN-13: 978-0821838044

Past Offerings

  • Offered in Jan-May, 2023 by Piyush P. Kurur

Course Metadata

Item Details
Course Title Computational Algebra and Number Theory
Course Code CS5634
Course Credits 3-0-0-3
Course Category PME
Proposing Faculty Piyush P Kurur
Approved on Senate 22 of IIT Palakkad
Course status New