Computer Algebra, Fall 2009, course documents
syllabus
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 padic numbers. For additional
information see the
worksheet on Factoring polynomials in Q[x] below.
 worksheet on xadic 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
padic Hensel lifting by xadic 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
padic numbers into a Hensel lift algorithm for the xadic
case.
Weeks 9  10.
Groebner basis
Factoring Integers