# Computer Algebra, Fall 2009, course documents

Weeks 1 and 2.

Weeks 3, 4, 5
• Modular algorithms and the Chinese Remainder theorem.
• Programming assignment: Modular algorithm for computing a determinant.
• The modular gcd algorithm. Read the worksheet The Extended Euclidean Algorithm.
• Study the algorithms in this worksheet and do the assignment about sqrfree. The worksheet explains how the following algorithms work:
• The Extended Euclidean Algorithm (only implemented for the case of positive integers, but it works in the same way for polynomials).
• How to do divisions modulo an integer p. Note: one can use a similar algorithm to do divisions modulo a polynomial.
• How to compute quotients and remainders.
• Euclidean Algorithm for polynomials.
• Chinese Remainder Theorem (only implemented for two integer moduli m1,m2. Of course a very similar algorithm would work when m1,m2 are polynomials).
• Do this assignment during class.
• Factoring in Fp[x] (continue with this in week 4 and 5).
• Short introduction to resultants.
• More details on resultants.
• The completion of a field with respect to a norm (if this webpage does not display correctly under Netscape under Unix then click here).
• worksheet on p-adic numbers. For additional information see the worksheet on Factoring polynomials in Q[x] below.
• worksheet on x-adic Hensel lifting.
• Factoring polynomials in Q[x].
• Project: Implement factorization in Q[x,y] in the same way as factorization in Q[x] is done in the worksheet. You may use Maple's "sqrfree" for squarefree factorization, and may only use Maple's "factor" for factoring univariate polynomials. Replace "icontent" by "content", replace p-adic Hensel lifting by x-adic Hensel liften, replace the bound on the length of the coefficients by a bound on the degree of the coefficients, etc. Turn the Hensel lift algorithm from the worksheet on p-adic numbers into a Hensel lift algorithm for the x-adic case.
Weeks 9 - 10.
Groebner basis
Factoring Integers