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
- 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
- More details on resultants.
Weeks 9 - 10.
- 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