# Computer Algebra II: Fast arithmetic and Factorization (Lecture)

Summer 2010

Description -
Course Details

How many field operations are needed to multiply two univariate polynomials
of degree *n* over some field *K*?
How about the number of field operations needed for factoring a polynomial
or computing a greatest common divisor of two polynomials?
Efficient algorithms for these and other problems were presented in
Computer Algebra I, but are they as efficient as can be?
It turns out that they are not. In Computer Algebra II we will present
faster algorithms, including some of the fastest algorithms known today
for solving algebraic problems.

## Course Details

- Lecturer: Manuel Kauers
- If you are regular JKU student, please register to this course via
KUSSS
- Exam/credits mode: will be discussed in the first meeting
- Time/Place:
- Wednesdays, 9.00--10.30, Seminar room Hagenberg
- First meeting: Wednesday, March 3
**No meeting on March 10**

- Prerequisits: Students are expected to be familiar with the material of
Computer Algebra I
- Literature:
*Modern Computer Algebra* by von zur Gathen and Gerhard,
Cambridge 1999;
*Algorithms for Computer Algebra* by Geddes, Czapor, and Labahn, Kluwer 1992.

## Material

Computing in homomorphic images (2010-04-21)

- Animation for solving a linear system over Q: sysQ.mp4
- Animation for solving a linear system over Z
_{p}: sysZp.mp4
- Animation for homomorphic preimages over Z: modZ.mp4
- Animation for homomorphic preimages over Q (rational reconstruction): modQ.mp4
- Demo for ratioal reconstruction: rationalReconstruction.nb
- Computation time depending on bitsize / Chinese remaindering illustration: main.pdf
- Demo for chinese remaindering and newton interpolation: chineseRemainder.nb
- Example linear system over Q(x) with 1D solution space: sys.m
- Implementation of a linear system solver using homomorphic images: LinearSystemSolver.m

top