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.
The following topics will be covered in this course
Basic algorithms for arithmetic, addition, multiplication and modular arithmetic. (4 lectures)
Euclid's algorithm, Chinese Remainder theorem and applications to problems like determinant computation, Gaussian elimination. (6 lectures)
Fields, Finite fields, Field of rationals, Polynomial factorisation over finite fields (6 lectures)
Hensel lifting and application to bivariate factoring (4 lectures)
Shortest vector problem and LLL algorithm. Application to factorisation of polynomial over rationals. (5 lectures)
Applications of polynomial factorisation. (5 lectures)
Multivariate system of polynomial equation and Grobner basis (7 lectures)
Algorithms from number theory and cryptography (5 lectures).
None. The course will start from the very basics.
To state and analysis algorithms for tasks like arithmetic, factorisation.
To apply the algorithms learned to tasks in cryptography, number theory etc.
- Modern Computer Algebra. Joachim von zur Gathen and Jurgen Gerhard. Cambridge University press, 2013. ISBN: 978-0521826464
Algorithmic Algebra. Bhubaneswar Mishra. Springer 1993, ISBN-10: 0387940901, ISBN-13: 978-0387940908
Ideal, Varities and Algorithms. David A. Cox, John Little, Donal O’Shea. Springer 2008. ISBN: 978-3-319-16721-3
An Introduction to Grobner Bases. Philippe Loustaunau, William W. Adams. American Mathematical Society, 1994 ISBN-10: 0821838040, ISBN-13: 978-0821838044
|Course Title||Computational Algebra and Number Theory|
|Proposing Faculty||Piyush P Kurur|
|Approved on||Senate 22 of IIT Palakkad|