Computer Algebra, Fall 2006, course documents

syllabus

Week 1.

• We will look at this Maple worksheet on sequences in class.
• We will look at this worksheet on polynomials and the use of the quotes: ' ' in class. If there's enough time we'll also look at the following worksheets: worksheet on rational functions, worksheet on modular arithmetic. Study the remaining worksheets for next time.
• Homework week 1.
• Programming in Maple.
• Another introduction to Maple and some exercises to test yourself (in the form of a pdf-file) with some of the answers.
• The Euclidean Algorithm.

• Programming assignment: multiplication of polynomials (this contains the homework for week 2).
• A sorting algorithm (called merge sort) based on the "divide and conquer" approach.
• Multiplying polynomials with the "divide and conquer" approach: the Karatsuba algorithm.
• Modular algorithms and the Chinese Remainder theorem.
• Programming assignment: Modular algorithm for computing a determinant (did this during class on the Wednesday of 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).

• Continue with the worksheet on factoring in Fp[x].
• Joint project: Implement factoring in Fp[x].
• 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.

• Lattices.
• General strategy for using LLL.
• Different way to factor in Q[x].
• Yet another example..
• Assignment
  m := 13^30; f1 := x^2+186754841457272102163578030635634*x+46880804142885485944842413874037;
  Find a polynomial g in Z[x] such that:
  • degree(g) < 8
  • coefficients of g have absolute values less than 300.
  • f1 divides g modulo m. So Rem(g, f1, x) mod m; is zero.
  Hint: Use the same method as in the second example of the last worksheet, but then add two vectors, namely C*[0 0 0 .. 0 m 0] and C*[0 0 0 .. 0 0 m]
• Lattice reduction algorithm for dimension 2.
• Solutions of a polynomial.
• Study the worksheets on resultants (see Weeks 4,5,6 above). Then look at solving equations with resultants.
• Resultant Assignments R1 and R2.
• Here is a text file that explains the basic notion of polynomial ideals and Hilbert's Nullstellensatz.
• Solving polynomial equations, polynomial ideals: Groebner basis.

• Applications of Groebner basis.
• in class assignments.

• Test on Wednesday Nov 29. The answers will become available after the test.
• Trager's factorization method for factoring over an algebraic extension of a field.

• Pollard's p-1 method for factoring integers
• Elliptic curves