# Module for [Scientific Computing]

[back] to List of Modules.

## [Computer Algebra I] - [2015 Sommer]

Module | Code MG19 | Name Computer Algebra I | ||

| Credit Points 8 CP | Workload 240 h | Duration 1 semester | Cycle 0 |

Methods | Lecture 4 h + Exercise course 2 h | |||

Objectives | To have a firm command of basic notions and methods in Computer Algebra | |||

Content | This lecture attends to the theory and complexity of basic mathematical algorithms and their implementations in computer algebra systems. Main topics are: - Fast arithmetic: complexity of basic operations, discrete Fourier transformation, fast multiplication, fast Euclidean algorithm, subresultants and polynomial remainder sequences, modular algorithms, computations with algebraic numbers, fast matrix multiplication - Prime factorisation and primality tests: Solovay-Strassen and Miller-Rabin primality test, AKS primality test, RSA algorithm, elementary factorisation methods, quadratic sieve, irreducibility tests for polynomials, Berlekamp algorithm, Zassenhaus algorithm, lattice basis reduction, factorisation of multivariate polynomials - Groebner Basis algorithms: Groebner Bases and reduced Groebner Bases, Buchberger algorithm, elimination theory, algorithms for elementary operations on ideals, computation of the dimension of an ideal | |||

Learning outcomes | Ability to solve problems in Computer Algebra and to present these solutions in problem sessions, ability to work with computer algebra systems | |||

Prerequisites | ||||

Suggested previous knowledge | Mathematics Bachelor, Algebra I (MB1) | |||

Assessments | Homework assignments, written or oral exam. Modalities for make-up exams are to be determined by the lecturer and will be announced at the beginning of the course. | |||

Literature | J. von zur Gathen, J. Gerhard: Modern Computer Algebra O. Geddes, S. R. Czapor, G. Labahn: Algorithms for Computer Algebra D. Cox, J. Little, D. O’Shea: Ideals, Varieties and Algorithms B. H. Matzat: Computeralgebra (lecture notes) |