ECE413 Computer Algebra I

• Fundamental Algorithms: Exact integer representation and arithmetic, polynomial representation and arithmetic.
• Fast multiplication: Karatsuba’s multiplication algorithm, the discrete and fast Fourier transform, and its applications.
• Euclid’s (extended) gcd algorithm.
• Applications of Euclid’s algorithm: Modular arithmetic, Fermat’s theorem, linear Diophantine equations, continued fractions.
• Modular arithmetic and interpolation: Evaluation and interpolation, the Chinese remainder algorithm, Hermite and Cauchy interpolation, Pade approximation, partial fraction decomposition, resultant and modular gcd algorithms.
• Public-key cryptosystems: RSA, Elliptic Curves and integer factorization algorithms.
• Factorization of Polynomials with Integer Coefficients: Factorization over Finite Fields and Hensel Lifting.

The purpose of this course is a first presentation of the algorithms and the mathematics involved in the various Computer Algebra Systems and to teach the students how to use the latter to symbolically solve scientific problems. More specifically, the course offers:

• Knowledge: Problem recognition and choice of the right method to solve it.
• Understanding: Detailed statement of the problem and choice of the appropriate system to solve it.
• Application: Experimentation and discovery of new facts.
• Analysis: Split a complex problem into simpler sub-problems.
• Synthesis: Re-organization and synthesis of the sub-problems.
• Evaluation: Comparison of the various methods and choice of the most appropriate.