Computer Algebra, Fall 2006, course documents
syllabus
Week 1.
Week 2
Week 3
 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).
Weeks 4, 5, 6
Weeks 78. This week we will study the padic numbers
Q_{p} and formal
power series
Q[[x]].
 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.
Weeks 1113
Week 14
Last week
Factoring integers.